Читайте также:
|
Алгебраической кривой (полиномом степени k) называют выражение
P (х) =C 0 +C 1 х+C 2 х2+…+Ck хk, (9.6)
где х – независимый параметр, k - степень полинома. Выражение (9.6) называются каноническим видом полиномов. При его использовании затрачивается минимальное число операций в расчётезначений P (х) в случае применения схемы Горнера, когда вычисления производятся по формуле P (х) = C 0 + х (C 1 +х (C 2 +…+ х (Ck -1 +Ck х)…)). Также канонический вид полиномов имеет наименьшее число коэффициентов, что минимизирует объем памяти, требуемой для его хранения.
Рассмотрим в общем виде задачу интерполирования (точного построения), в которой требуется точно выполнить набор условий, накладываемых в отдельных узловых точках, при помощи единой алгебраической кривой P (х) наименьшей степени k.
Постановку задачи можно сформулировать следующим образом:
построить полином P (х) наименее возможной степени k, который:
1) проходит через заданные точки `P 0 =(х 0, у 0) ,`P 1=(х 1, у 1), …,`Pn = (хn, уn);
2) в некоторых точках `Pi =(хi, уi) ,` производные полинома P (х) до некоторой степени j должны принимать заданные значения: P¢(х i)= уi ¢,..., P j(х i)= уi j .
Для отдельных частных случаев решение задачи найдено в явной форме (в виде готовых формул, не требующих предварительного составления и решения уравнений). Так, при простом прохождении функции через узлы без учета ее производных в узлах (пункт 2 общей постановки) решение рассмотренной задачи дают интерполяционные полиномы Лагранжа и Ньютона. При дополнительном задании первых производных в узлах решение дает полином Эрмита. Данные полиномы дают решение в готовом виде. Их общим недостатком является увеличенное число элементарных операций, затрачиваемых при расчете значений по сравнению с полиномом канонического вида. Его можно устранить, применяя группировку слагаемых при степенях параметра х.
Рассмотрим общее решение сформулированной задачи интерполирования для полинома Р(x) каноническоговида минимально возможной степени k на некотором наборе узлов x 0, x 1 ,…, xn.
При расчете минимального значения k исходят из следующих соображений: число неизвестных коэффициентов С0, C1, …,Ck в полиноме равно (k+ 1 ). Общее число условий, накладываемых на функцию в узлах, складывается из:
1) количества заданных точек `P 0 ,`P 1 ,…,`Pn – их число равно (n+ 1 );
2) общего числа производных 
, заданных в этих точках.
Решение задачи интерполирования всегда существует и является единственным, если k+ 1 = n+ 1 + . При выполнении этого условия число неизвестных равно числу уравнений. Отсюда следует предварительная величина минимальной степени интерполирующего полинома:
k=n+ . (9.7)
После определения k решается задача об определении коэффициентов полинома `С = { С 0 ,С 1 ,…,Сn }. Для этого составляется система из k уравнений, каждое из которых образуется подстановкой значения x = xi в условие первого типа y(xi) = yi, что дает уравнение вида: C 0 +C 1 xi+C 2 xi 2 +…+Ckxik=yi.
Для раскрытия условия на первую производную y¢(xi) = yi¢ выполняем подстановку x = x1 в производную 
. Получаем уравнение: C 1 + 2 C 2 xi +…+kCkxik- 1= y i¢.
Производные более высоких порядков раскрываются аналогично. Итоговую систему линейных уравнений можно представить в виде:
A `C=`Y, (9.8)
где ` C=(C 0, C 1 ,…,Ck) – искомый вектор коэффициентов полинома,
`Y – вектор заданных точечных значений функции и ее производных,
A – матрица коэффициентов.
Искомый вектор неизвестных коэффициентов равен:
C = A- 1 ×`Y, (9.9)
где A - 1 – матрица, обратная к А.
Пример 1. Заданы:
1) значения полинома в трех узлах: y (x 0) = y 0; y (x 1) =y 1; y (x 2) =y 2 и
2) значение первой производной в узле x 0: y¢ (x 0 )=y 0 ¢.
Необходимо построить интерполирующий полином наименее возможной степени.
Решение.
1.Определение степени полинома k. Число n= 2, суммарное число заданных значений производных = 1. Следовательно, по формуле (9.7) k= 3 и полином имеет вид: P(x) = C 0 + C 1 x + C 2 x 2 + C 3 x 3, где (С 0, C 1, C 2, C 3 ) - постоянные коэффициенты.
2.Определение коэффициентов полинома. Из условий вида 1) подстановкой вместо х значений х0, х1, х2 получаем уравнения
C 0 +C 1 x 0 +C 2 x 02 +C 3 x 03 = y 0;
C 0 +C 1 x 1 +C 2 x 12 +C 3 x 13 = y 1;
C 0 +C 1 x 2 +C 2 x 22 +C 3 x 23 = y 2.
Из условия вида 2) подстановкой х = х 0в P¢(x) = C 1 + 2 C 2 x + 3 C 3 x2 получаем уравнение C 1 + 2 C 2 x 0 + 3 C 3 x 02 = y 0 ¢.
Объединяя полученные уравнения, получаем систему вида (9.8), где
; 
; 
.
Решением системы является вектор ` C=A-1 *`Y.
Замечание. При специальном задании геометрических условий возможны случаи, когда реальная степень полинома меньше значения, задаваемого формулой (9.7). Например, если в приведенном выше примере задать условия вида:
y (1)=0; y (2)=1; y (3)=2; 2) y ¢(1)=1;то при этом
; 
; 
; P (x) = x- 1; k = 1 < 3.
Таким образом, в данном частном случае реальная степень интерполирующего полинома равна 1. Геометрический смысл примера понятен из Рис.9.1: точки `Р 0, `Р 1, `Р 2 лежат на прямой y= (x- 1), угол наклона производной y¢ (x 0) также равен углу наклона этой прямой, поэтому в данном случае вместо кубической параболы (k= 3) минимальную степень полинома получаем на наклонной прямой, имеющей k= 1.
Рис.9.1
Если рассматривать частный случай y (1)=1; y (2)=1; y (3)=1; 2) y ¢(1)=0;
то векторы `Y и `С будут следующими:
; 
.
Интерполирующий полином примет вид: P (x) = 1. В данном случае реальное значение k= 0, т.к. все точки лежат на прямой y= 1 и угол наклона производной равен 0 (Рис. 9.2).
Рис. 9.2
В обоих приведенных примерах имеет место дублирование условий, наложенных на интерполирующих полином, поскольку некоторые из них оказываются излишними, описывающими объект, уже полностью определённый предыдущими условиями. Рассмотренные примеры показывают, что окончательное значение степени полинома k может быть уточнено только после расчета его коэффициентов.
Расчет одного значения полинома канонического вида степени k по схеме Горнера требует выполнения k сложений и k умножений. Сложность вычисления линейная по k - О(k 1).
Вопросы для проверки знаний.
1. Какое выражение называют алгебраической кривой (полиномом)?
2. В чем заключаются преимущества канонической формы представления полиномов?
3. Для каких частных случаев задачи интерполирования по заданным узлам существуют явные решения в формульном виде?
4. По какой формуле может быть рассчитана предварительная величина минимальной степени интерполирующего полинома?
5. Каким образом составляются линейные уравнения по условиям, заданным в узлам на интерполирующий полином?
6. Почему после расчета коэффициентов полинома его степень может оказаться меньше ее предварительной минимальной величины?
Дата добавления: 2015-02-16; просмотров: 40 | Поможем написать вашу работу | Нарушение авторских прав |