корнюшин.численные методы

31

2.2.9. Метод Лобачевского нахождения корней алгебраических многочленов

Главное достоинство этого метода состоит в том, что он не требует знания о приближенных значениях корней. Он применяется в тех случаях, когда многочлен имеет различные действительные корни.

Метод реализуется в два этапа. Если корни многочлена удовлетворяют неравенству

Если соотношения (16) не выполняются, то необходимо выполнить предварительный этап, называемый процессом квадрирования и суть которого состоит в следующем.

Запишем разложение многочлена на сомножители

Запишем многочлен, корни которого отличаются от корней данного многочлена знаками:

идея процесса квадрирования в том, что если корни различны, то разница по модулю при квадрировании существенно возрастает.

Выразим коэффициенты многочлена, полученного в результате квадрирования через коэффициенты исходного многочлена. Итак, пусть задан многочлен

a0 xn +a1 xn−1 +a2 x n−2 +... +an−1 x +an. (21)

Заменим х на -х:

a0 (−1)n x n +a1 (−1)n−1 x n−1 +... +an−1 (−1)x +an.

Домножим последнее соотношение на (-1)n:

Перемножая (21) и (22), получаем:

32

a02 x 2n +(−a12 +2a0 a2 )x 2n−2 +(a22 −2a1a3 +2a0 a4 )x 2n−4 +... +an2 .

Сделаем замену переменной x=-x2:

an2 .

Процесс квадрирования можно повторить сколь угодно раз. Каков же критерий останова?

являются результатами квадрирования, т.е. (24) получается из (23) в результате очередного квадрирования. Пусть корни многочлена (23) уже настолько по модулю отличаются друг от друга, что можно применить (18), т.е.

33

2.3. Теория интерполирования

Пусть на некотором сегменте [a,b] вещественной оси заданы точки {xi }im=1 , причем x1=a;

xm=b, и в этих точках заданы некоторые действительные значения {f (xi )}im=1 . Требуется найти

такую непрерывную на [a,b] функцию φ(x), которая удовлетворяла бы следующим условиям: φ(xi)=f(xi), i=1, 2,…,m. Задача нахождения функции φ(x), т.е. задача нахождения значений функции между заданными точками и есть задача интерполирования. При этом функция φ(x) называется

интерполирующей (интерполяционной), а точки {xi }im=1 – узлами интерполяции.

Интерполяция применяется во многих задачах, связанных с вычислениями. Укажем некоторые из этих задач.

Обработка результатов физического эксперимента – построение приближенных формул для характерных величин по табличным данным, полученным экспериментально.

Построение приближенных формул по данным вычислительного эксперимента. Здесь возникают нестандартные задачи интерполяции, т.к. обычно пишутся формулы возможно более простой структуры.

Субтабулирование, т.е. сгущение таблиц. Применяется в тех случаях, когда непосредственное вычисление функции затруднено или когда имеется мало экспериментальных данных. В машину вводится наибольшая таблица, а нужные при расчетах значения функции находятся по мере необходимости по интерполяционной формуле.

Интерполяция применяется также в задаче обратного интерполирования: задана таблица yi=y(xi); найти xi как функцию от yi. Примером обратного интерполирования может служить задача о нахождении корней уравнения.

Интерполяционные формулы используются также при вычислении интегралов, при написании разностных аппроксимаций для дифференциальных уравнений на основе интегральных тождеств.

2.3.1. Задача интерполирования в линейном пространстве

Пусть R – линейное пространство непрерывных действительных функций {f(x)} на [a,b]. Пусть конечная или счетная система функций {φj(x)} R такова, что любой конечный набор из

этих функций линейно независим. Рассмотрим функции {ϕ j (x)}nj =0 . Любое выражение вида A(x)=a0φ0(x)+a1φ1(x)+…+anφn(x), где {aj} – действительные числа, называется "обобщенным" полиномом по системе функций {ϕ j (x)}nj =0 . Пусть на [a,b] заданы n+1 точка {xi }in=0 , и пусть в этих точках заданы значения f(xi), i=0, 1,…, n. Требуется построить "обобщенный" многочлен А(х) по системе функций {ϕ j (x)}nj =0

Определение. Система функций {ϕ j (x)}nj =0 . называется системой Чебышева (Т-системой)

на [a,b], если любой полином А(х) по этой системе функций имеет на сегменте [a,b] не более n нулей, в предположении, что хотя бы один из коэффициентов полинома отличен от нуля.

Теорема. Необходимое и достаточное условие того, чтобы существовал обобщенный интерполяционный полином по заданной системе функций {ϕ j (x)}nj=0

точках {xi }in=0 , заданных на [a,b], и при любых значениях f(xi)=αi, заключается в том, чтобы система функций {ϕ j (x)}nj=0 , была Т-системой. При этом интерполяционный полином

единственный.

Утверждение теоремы эквивалентно следующему утверждению: каковы бы ни были числа {xi }in=0 и каковы бы ни были числа αi, система уравнений вида

34

с неизвестными a0, a1,…, an должна иметь решение. Последняя задача эквивалентна тому, что главный определитель этой системы

должен быть отличен от нуля при любых различных {xi }in=0 на [a,b].

Покажем, что необходимое и достаточное условие того, чтобы выполнялось (1) заключается в следующем: система функций {ϕ j (x)}nj=0 должна быть системой Чебышева.

Пусть {ϕ j (x)}nj=0 есть Т-система. Покажем, что выполняется (1). Предположим противное.

Тогда между столбцами определителя существует линейная зависимость, т.е. найдутся числа

n

{bi }in=0 такие, что ∑bi2 ≠ 0, т.е. хотя бы одно bi ≠ 0, и выполняются следующие равенства:

i=0

b0φ0(xi)+b1φ1(xi)+…+bnφn(xi)=0, i=0,1,…,n.

Последнее эквивалентно тому, что существует полином, который обращается в 0 в n+1 точках. Поскольку Т-система имеет n нулей, то получили противоречие, которое и доказывает справедливость выполнения соотношения (1).

Пусть теперь выполнено (1). Докажем, что {ϕ j (x)}nj=0 – Т-система. Предположим противное. Тогда найдутся n+1 различных точек {xi }in=0 на [a,b] таких, что некоторый полином C(x)= ∑nk =0 ck ϕk (x) имеет n+1 нулей в точке xi (при этом ∑in=0 ci2 ≠ 0) . Тогда имеет место система уравнений

c0φ0(xi)+c1φ1(xi)+…+cnφn(xi)=0, i=0,1,…,n.

Но это однородная система уравнений, и она имеет отличные от нуля решения {ci }in=0

тогда и только тогда, когда главный определитель приведенной системы уравнений отличен от нуля. Поскольку этим определителем является определитель (1), то опять пришли к

противоречию. Предположение не подтвердилось, поэтому {ϕ j (x)}nj=0 – Т-система.

Итак, интерполяционный полином существует. Единственность существующего полинома вытекает из того, что система уравнений вида

n

∑ak ϕk (xi ) =αi , i=0,1,…,n

k =0

с неизвестными {ak} может иметь только одно решение, т.к. главный определитель этой системы отличен от нуля, и система является определенной.

Пример. Пусть ϕi (x) = xi , i=0,1,…,n. Показать, что система функций {xi }in=0 есть Т- система на всей вещественной оси.

Пусть {x j }nj =0 – множество различных точек на действительной оси. Необходимое доказательство сводится к доказательству следующего факта:

36

n

Определим старший коэффициент этого многочлена. Обозначим ωn+1 = ∏(x − x j ). Тогда

j=0

Φj (x) = a ωn+1 (x) . Воспользовавшись равенством Фj(xj)=1, определим значение коэффициента a:

x− x j

которое представляет собой формулу интерполяционного полинома Лагранжа.

2.3.3. Формула остаточного члена полинома Лагранжа

Если о функции известно только то, что она непрерывна, то никаких оценок интерполяции сделать нельзя. Предположим, что функция f(x), значения которой заданы в точках {xi }in=0 на [a,b]

непрерывно дифференцируема, и при этих условиях на функцию выведем формулу остаточного члена Rn(x)=f(x)-Ln(x), где Ln(x) – интерполяционный полином Лагранжа по системе функций

{x j }nj=0 . Введем в рассмотрение функцию, заданную на [a,b]:

φ(z)=f(z)-Ln(z)-K(z-x0)(z-x1)…(z-xn),

где K – некоторая константа, значение которой требуется определить.

Найдем R(x) в некоторой фиксированной точке x ≠ xj, j=0,1,…,n, и подберем K таким образом, чтобы в этой точке φ(z) обращалась в ноль, т.е.

При полученном значении K функция φ(z) обращается в ноль не менее, чем в n+2 различных точках: x, {xi }in=0 ; тогда φ'(z) имеет не менее (n+1) действительных корней (нулей);

φ''(z) – не менее n нулей и т.д., φ(n+1)(z) – не менее одного. Пусть ξ – действительный корень φ(n+1)(z), т.е. φ(n+1)(ξ)=0. Из формулы для φ(z) вытекает, что в любой точке z выполняется

соотношение φ(n+1)(z)=f(n+1)(z)-K(n+1)!, откуда, полагая z=ξ, получаем K = f (n+1) (ξ) , что, с учетом

(n +1)!

соотношений Rn(x)=f(x)-Ln(x), ωт+1(x)=(x-x0)(x-x1)…(x-xn), приводит к формуле остаточного члена полинома Лагранжа

2.3.4. Оценка остаточного члена формулы Лагранжа

Полиномы Чебышева.

Пусть по-прежнему функция f(x), значения которой заданы в точках {xi }in=0 на [a,b]

37

обеспечивалось как можно меньшее значение max ωn+1 (x) ? Ответ на эти вопросы следует искать,

изучая свойства полиномов Чебышева. Полиномы Чебышева задаются следующим соотношением: Tn(x)=cos(narccosx). Получим рекуррентное соотношение для вычисления значений полиномов Чебышева, для чего проведем следующие расчеты:

T0(x)=1; T1(x)=cos(arccosx)=x; T2(x)=cos(2arccosx)=2cos2(arccosx)-1=2x2-1.

Обозначая θ=arccosx (или x=cos), имеем

cos(n-1)θ+cos(n+1)θ=2cosθcosnθ cos(n+1)θ=2cosθcosnθ-cos(n-1)θ,

или

Tn+1(x)=2xTn(x)-Tn-1(x). (3)

Найдем корни многочлена Tn(x) и его производной T'n(x). В принятых обозначениях имеем:

Tn(x)=cos(narccos(cosθ))=cosnθ; cosnθ=0; θk=π(2k+1)/(2n); xk=cos[π(2k+1)/(2n)], k=0,1,…,n-1.

T'n(x)=nsin(narccosx)/ 1 − x2 ; sin(arccosx)=0; xj=cos(jπ/n), j=1,2,…,n-1.

Итак, все n корней многочлена Чебышева Tn(x) расположены на сегменте [-1,1]; экстремальные значения многочлена Tn[cos(jπ/n)]=cos(jπ)=(-1)j, j=1,2,…,n-1; на концах сегмента Tn(1)=1, Tn(-1)=(-1)т. Поэтому многочлен Чебышева n+1 раз достигает на [-1,1] экстремальное значение (-1)i с последовательным чередованием знаков.

Возьмем в качестве многочлена ωn+1(x) на [-1,1] следующий:

Анализ формулы (3) приводит к выводу, что старший коэффициент многочлена Tn(x) равен 2n-1. Тогда многочлен ωn+1(x) имеет единичный старший коэффициент, т.е. ωn+1(x) на [-1,1] уклоняется от нуля не более, чем на 1/2n.

Несложно доказать [1], что никакой другой многочлен Pn+1(x) с единичным старшим коэффициентом не уклоняется от нуля на [-1,1] менее, чем на 1/2n. Таким образом, среди всех многочленов ωn+1(x) наименее уклоняется от нуля многочлен 1/2nTn+1(x), который на сегменте [- 1,1] не превосходит величины 1/2n.

Итак, если в качестве узлов интерполяции выбрать корни многочлена Чебышева, то остаточный член формулы Лагранжа принимает следующий вид:

2.3.5. Понятие о разделенных разностях

Пусть дана непрерывная на [a,b] функция f(x) и узлы интерполирования {x j }nj=+11 .

Разделенными разностями первого порядка называются следующие величины:

Разделенные разности второго порядка суть

Тогда по индукции разделенная разность (k+1)-го порядка есть

38

Свойства разделенных разностей:

1) для разделенных разностей k-го порядка имеет место формула

2)разделенная разность k-го порядка f[xj, xj+1,…, xj+k]=Fk(f) есть линейный функционал, т.е.

Fk[f(x) ± g(x)]=Fk[f(x)] ± Fk[g(x)], Fk[af(x)]=aFk[f(x)];

3)разделенная разность есть симметричная функция своих аргументов, т.е. аргументы можно переставлять, например,

f[xj, xj+1,…,xj+k]= f[xj+1, xj,…,xj+k];

4)разделенные разности k-го порядка от функции xn есть однородные многочлены своих аргументов порядка (n-k), разделенные разности n-го порядка тождественно равны 1, а выше n- го порядка равны 0;

5)учитывая, что алгебраический многочлен есть сумма степенных функций, получаем, что для любого алгебраического многочлена степени n разделенные разности n-го порядка равны const, а разделенные разности (n+1)-го порядка равны 0.

2.3.6. Интерполяционная формула Ньютона

Пусть дана непрерывная на [a,b] функция f(x) и узлы интерполяции {x j }nj =0 . Пусть Lk(x) –

интерполяционный полином Лагранжа для функции f(x), построенный по узлам {x j }kj=0 .

Рассматривая преобразование Ln(x)=L0(x)+[L1(x)-L0(x)]+[L2(x)-L1(x)]+…+[Ln(x)-Ln-1(x)], где Lk(x)-Lk- 1(x)=A(x-x0)(x-x1)…(x-xk-1), определим значение старшего коэффициента A, положив для этого x=xk:

Интерполяционная формула Ньютона имеет следующий вид:

Hn(x) ≡Ln(x)=f(x0)+(x-x0)f[x0, x1]+(x-x0)(x-x1)f[x0, x1, x2]+ +…+(x-x0)(x-x1)…(x-xk)f[x0, x1,…xk+1]+…+(x-x0)(x-x1)…(x-xn-1)f[x0, x1,…xn].

Эта формула очень удобна, т.к. при добавлении новых точек интерполирования надо лишь добавлять новые слагаемые, не меняя старой записи. Используя тот факт, что разделенные разности – симметричные функции своих аргументов, новые узлы интерполирования можно брать в любом порядке, в том числе и в промежутках между старыми. Особенно удобна формула Ньютона при составлении таблиц.

2.3.7. Основные задачи в теории интерполирования

В теории интерполирования можно выделить две основные задачи. Первую назовем "задачей приближения функции в точке". Для поиска решения этой задачи характерно стремление

по заданным значениям функции f(x) в точках {x j }nj=+11 на [a,b] получить возможно более точное

значение функции в некоторой фиксированной точке x [a,b]. Такая задача возникает при вычислении значения функции по таблице, когда значение x не совпадает с узлом таблицы.

39

Вторая задача состоит в "равномерном приближении функции на сегменте". При решении этой задачи стремятся получить возможно меньшее по модулю максимальное уклонение функции от интерполяционного полинома на всем сегменте [a,b]. При решении этой задачи большую роль играют оценки остаточных членов интерполяционных формул.

Прежде чем воспользоваться интерполяционной формулой, необходимо ответить на следующие вопросы.

1) Какие следует выбрать узлы?

В качестве узлов лучше всего брать корни многочлена Чебышева. Этот подход справедлив для равномерного приближения на отрезке. Если речь идет о таблицах, в подавляющем большинстве случаев выбирают равномерное распределение узлов.

2)Какой выбирается класс функций для интерполирования?

системы функций переходят сами в себя при замене переменной x на x+a, т.е. эти системы функций не зависят от начала отсчета. Кроме того, система степенных функций переходит сама в себя и при замене переменной x на ax, т.е. она не зависит от масштаба.

3)Какова желаемая точность результатов?

Точность выбирается исходя из задачи. Вычислительная практика показывает, что вопрос о необходимой точности решения надо рассматривать не только перед вычислительным процессом, но и в ходе его, особенно на том этапе, когда полученные результаты преобразуются к виду, поставленному алгоритмистом.

4)Каким критерием согласия следует руководствоваться?

Классический критерий согласия, который используется в теории интерполирования следующий: требование точного совпадения интерполяционного многочлена со значениями функции в заданных точках. Если же рассматривать интерполирование более широко (например, использование интерполяционных формул при численном интегрировании), то можно использовать и другие критерии согласия: Приведем три таких критерия:

•минимизация суммы квадратов уклонений от значений функции в заданных точках, т.е. минимизация ошибки;

•минимизация уклонения интерполяционного полинома от функции на всем сегменте задания функции;

•совпадения в заданных точках значений интерполяционной функции не только со значениями функции, но и совпадение в этих точках значений их производных (сплайн-интерполяция).

2.3.8. Сплайн-интерполяция

Рассмотрим случай кусочно-полиномиальной интерполяции, когда между любыми соседними узлами интерполяции строится кубический полином (кубическая сплайнинтерполяция). Коэффициенты полинома на каждом интервале определяются из условий сопряжения в узлах:

40

Вычислим производные

f'(x)=bi+2ci(x-xi-1)+3di(x-xi-1)2, f''(x)=2ci+6di(x-xi-1), x [xi-1, xi]

и потребуем их непрерывности при x=xi. Это требование после несложных преобразований приводит к следующим соотношениям:

bi+1=bi+2cihi+3dih i2 , ci+1=ci+3dihi, i=1, 2,…, n-1. (5)

Общее число неизвестных коэффициентов, очевидно, равно 4n, число уравнений (4), (5) равно 4n-2. Недостающие два уравнения получаем из условий (2) при x=x0 и x=xn:

с1=0, cn+3dnhn=0.

Выражая из (5) di=(ci+1-ci)/(3hi), подставляя это выражение в (4) и исключая ai=yi-1, получим

bi=(yi-yi-1)/hi-hi(ci+1+2ci)/3, i=1, 2,…, n-1, bn=(yn-yn-1)/hn-2hncn/3.

Подставив теперь выражения для bi, bi+1 и di в первую формулу (5), после несложных

Условие cn+1=0 эквивалентно условию cn+3dnhn=0 и уравнению ci+1=ci+3dici при i=n. Разностное уравнение (6) с условиями (7) решаются методом прогонки.

Можно ввести понятие сплайна порядка m как функции, которая является полиномом степени m на каждом из отрезков сетки и во всех внутренних узлах сетки удовлетворяет условиям непрерывности функции и производных до порядка m-1 включительно. Обычно для интерполяции используются случаи m=3 (рассмотренный выше кубический сплайн) и m=1 (линейный сплайн, соответствующий аппроксимации графика функции y(x) ломаной, проходящей через точки (xi, yi)).