Численные методы. Соснин (2005) (1160462), страница 11
Текст из файла (страница 11)
Зная, что x∗ = 1 подходит, не будем утруждать себялокализацией корней, а просто покажем, как проходят итерационные процессы различных методов.Метод простой итерации.Возьмем отрезок [ 23 , 43 ] и зададим на нем итерационный процесс:xk+1 = S(xk ),где зададим S(x) = x−τ (x3 −1). Рассмотрим, какие ограничения накладываются на τ в этом примере:S 0 (x) = 1 − 3τ x2 .Потребуем выполнение достаточного условия сходимости:|S 0 (x)| < 1 ⇐⇒ −1 < 1 − 3τ x2 < 1.Отсюда ограничение на τ таково:2 3= .0<τ <3x2 x= 483Возьмем τ = 0.25, тогда S(x) = x −процесса, взяв x0 = 1.1 :k012345x3 − 1.
Распишем первые несколько шагов итерационного4xk1.11.017251.004091.001011.000251.00006xk − x∗0.10.017250.004090.001010.000250.00006Видно, что скорость сходимости не очень высокая. Однако на третьем и четвертом шаге уже можноприменить коррекцию Эйткена:xk+2 = xk+2 −Тогда получим такую таблицу:(xk+2 − xk+1 )2.− 2xk+1 + xkxk+23.6.
РЕШЕНИЕ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙxk − x∗0.10.017250.004090.0000680.000001xk1.11.017251.004091.0000681.000001k0123455Видно, что точность существенно возросла.Метод Ньютона.Согласно канонической форме метода Ньютона,xk+1 = xk −f (xk ).f 0 (xk )Зная, что f (x) = x3 − 1, а f 0 (x) = 3x2 , получим такую формулу:xk+1 = xk −(xk )3 − 1.3(xk )2Таблица приближений такова:k0123xk1.11.008821.000081.000000006xk − x∗0.10.008820.000080.000000006Здесь уже заметно, что скорость сходимости — квадратичная.Пример 3.3. (Метод Ньютона для систем уравнений)Рассмотрим следующую систему нелинейных уравнений:F (x, y) = x2 + y 2 − 4 = 0;G(x, y) = xy − 1 = 0.(3.17)На первом этапе (разделение корней) получаем 4 корня. Это можно показать, нарисовав графикисоответствующих кривых.2134Возьмем начальное приближение для поиска одного из корней таким:x0 = 2, y 0 = 0.Решать систему будем методом Ньютона.
Линеаризованные уравнения имеют вид:∂F k k(x , y )∆xk +∂x∂G k k(x , y )∆xk +∂x∂F k k(x , y )∆y k∂y∂G k k(x , y )∆y k∂y= −F (xk , y k );k = 0, 1, . . .kk= −G(x , y ),56Глава 3. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙУчитывая вид системы (3.17), можно найти частные производные:∂F= 2x,∂x∂G=y,∂x∂F= 2y;∂y∂G=x.∂yПодставив их в (3.17), можно найти приращения, решив систему:2xk ∆xk + 2y k ∆y k = 4 − (xk )2 − (y k )2 ;y k ∆xk + xk ∆y k = 1 − xk y k .и подставить в определение итерационного процесса: k+1x= xk + ∆xk ;y k+1 = y k + ∆y k .Получим следующую последовательность итерационных приближений:N1xk2yk0F0G−1220.50.25031.930.517−0.0077−0.0022∆xk01−15...∆y k0.5160...Как видно из приведенной таблицы, процесс очень быстро сходится. Об этом можно судить повеличине функций F (x, y) и G(x, y), так как мы решаем уравнения F (x, y) = 0 и G(x, y) = 0.Как же работает метод Ньютона? Дадим геометрическую интерпретацию этого метода.
В каждойтекущей точке (xk , y k ) к поверхностям z = F (x, y) и z = G(x, y) строятся касательные плоскости.Потом рассматриваем линии пересечения этих плоскостей с плоскостью z = 0 — это две прямые. И взаключение, определяем точку пересечения полученных прямых как новое, k + 1 значение.Глава 4Интерполяция и приближениефункцийВ этой главе мы будем восстанавливать функцию по значениям в некоторых заданных точках.Итак, пусть на отрезке [a; b] задан набор точек (n + 1 точка).
Эти точки называют узлами интерполяции. Занумеруем их в следующем порядке a = x0 < x1 < . . . < xn = b, и пусть в каждойиз этих точек известно f (xk ) = fk , k = 0, n. Наша задача заключается в том, чтобы вычислитьприближенные (с некоторой точностью) значения функции между значениями в узлах интерполяции.Опираясь на эти сведения, построим на том же отрезке функцию Φ(x), которую назовем интерполянтой — она и будет служить приближением исходной функции. Не любая Φ(x) нам подойдет —потребуем, чтобы она была легко вычислима, и совпадала с исходной функцией в узлах интерполяции: Φ(xk ) = f (xk ), k = 0, n. Иногда, правда, от последнего условия отказываются — тогда говорято построении наилучшего приближения.
Впрочем, вся терминология будет объясняться по ходудела.Построим интерполянту. Введем базисные функции ϕi (x), i = 0, m — линейно независимыеэлементы в нашем пространстве функций. Φ(x) будем строить как линейную комбинацию базисныхфункций ϕi (x) :mXΦ(x) =ai ϕi (x).i=0В качестве базисных функций мы можем выбрать следующие:1.
Степенные функции: ϕi (x) = xi ;2. Тригонометрические функции: в случае интерполяции периодических функций с периодом, кπixпримеру, 2l лучше взять sin πixl и cos l ;3. Дробно-полиномиальные функции.Интерполяция алгебраическими многочленамиОдним из наших первых требований было совпадение значений интерполянты и исходной функциив узлах сетки. Записав интерполянту через базисные функции (пусть их будет n + 1 — столько же,сколько узлов), получим такие уравнения:nXai ϕi (xk ) = f (xk ), k = 0, n.i=057(4.1)58Глава 4. ИНТЕРПОЛЯЦИЯ И ПРИБЛИЖЕНИЕ ФУНКЦИЙОтносительно ai мы получили СЛАУ с n + 1 неизвестными, так как ϕi (xk ) и f (xk ) заданы.
Условием разрешимости в данном случае является то, что определитель системы (4.1) отличен от нуля. Приэтом решение будет существовать и оно будет единственным. Определитель матрицы системы будетвыглядеть так: ϕ0 (x0 ) ϕ1 (x0 ) . . . ϕn (x0 ) ϕ0 (x1 ) ϕ1 (x1 ) . . . ϕn (x1 ) (4.2). . . . . . .ϕ0 (xn ) ϕ1 (xn ) .
. . ϕn (xn )Будем брать в качестве базисных функций степенные. Тогда (4.2) — это определитель Вандермонда:1 x0 x20 . . . xn0 1 x1 x21 . . . xn1 = (x1 − x0 )(x2 − x0 ) . . . (xn − x0 )(x2 − x1 )(x3 − x1 ) . . . (xn − xn−1 ) =. . . . . . .1 xn x2n . . . xnn Y=(xm − xk ) 6= 0, если xi 6= xj ∀ i 6= j.06k<m6nОткуда следует необходимое и достаточное условие, накладываемое на систему (4.1): все узлы интерполяции должны быть различными, тогда решение существует и единственно.Оно даст коэффициенты ai , и мы получим выражение для Φ(x). Существуют различные видызаписи одного и того же многочлена:Ln (x) =nXCk (x)fk .k=0— это интерполяционная формула Лагранжа. Коэффициенты для нее вычисляются по формуле:nYCk (x) =i=0i6=knY(x − xi ).(xk − xi )i=0i6=kЕсли обозначить ω(x) = (x − x0 )(x − x1 ) .
. . (x − xn ), то получим более короткую форму записи длякоэффициентов:ω(x)Ck (x) =.(x − xk )ω 0 (xk )Проверим, что этот многочлен и есть наша функция. В узлах интерполяции:1, k = j;Ck (xj ) =0, k 6= j.Поэтому совпадение значений функции с заданными в узлах сетки выполняется:Ln (xk ) = fk = F (xk ).Если у исходной функции производные ограничены, то формула для погрешности будет иметь вид:|f (x) − L(x)| 6Mn+1|ω(x)|,(n + 1)!где Mn+1 = sup |f (n+1) (x)|.x∈[a; b]59Теперь допустим, что нам известны f (1) (xk ), f (2) (xk ), . . .
, f (Nk −1) (xk ) — в каждом узле Nk значений функции и ее производных. Если опираясь на эти данные, строить интерполянту, то всего будетN0 + N1 + . . . + Nn условий. Пусть интерполянтой будет многочлен Hm (x) степени m, причем этотмногочлен будет удовлетворять условиям:(i)Hm(xk ) = f (i) (xk ),где k = 0, n,i = 0, Nk − 1.(4.3)В силу того, что число коэффициентов многочлена Hm (x) = a0 + a1 x + .
. . + am xm равно m + 1, аусловий N0 + N1 + . . . + Nn , то для определения коэффициентов степень полинома должна быть равнаN0 + N1 + . . . + Nn − 1.Эта задача называется интерполированием с кратными узлами. Многочлен, полученный врезультате решения этой задачи, называется интерполяционным многочленом Эрмита1 .Покажем, что эта задача разрешима единственным образом. Задача поиска коэффициентов сводится к решению СЛАУ (4.3), в которой общее число уравнений равно N0 + N1 + .
. . + Nn − 1.Для доказательства единственности решения СЛАУ рассмотрим однородную систему:(i)Hm(xk ) = 0,где k = 0, n, i = 0, Nk − 1.(4.4)Если решение этой системы — тривиальное, то решение исходной задачи существует и единственно.Из (4.4) имеем, что xk — корень полинома Эрмита с кратностью Nk , тогда общее число корней с учетомкратности будет равно N0 + N1 + . . . + Nn — что на единицу больше степени многочлена.
Это означает,что полином тождественно равен нулю, и, соответственно, равны нулю все его коэффициенты. Мыполучили, что однородная система имеет только тривиальное решение, а следовательно, сам полиномсуществует и единствен.Формула2 , соответствующая интерполяционному многочлену Эрмита будет иметь вид:−i−1n NXnnk −1 NkXXY f (i) (xk )∂l Yi+lNjHm (x) =(x − xj ) · l(x − xj )−Nj |x=x . i! · l! (x − xk )k∂x j=0i=0j=0k=0l=0j6=kj6=kЕсли взять в качестве параметра Nk = 1, то получится интерполяционная формула Лагранжа.Возникает вопрос: действительно ли при стремлении степени m к бесконечности соответствующиймногочлен все лучше описывает свойства приближаемой функции?Сходимость интерполяционного процесса(n)Введем обозначение последовательности сеток: Ωn = {xk , k = 0, n}.Пусть у нас для любой такой сетки имеется набор табличных данных f (xk ). Рассмотрим последовательность Ω0 = {x00 }, Ω1 = {x10 , x11 }, .
. . , Ωn = {xn0 , . . . , xnn }, и на каждом из этих множествпостроим интерполяционный многочлен Лагранжа. Проверим, выполняется ли, что Ln (x) −→ f (x).Определение. Интерполяционный многочлен Лагранжа сходится в точке x к функции f (x),если существует предел lim Ln (x) = f (x).n→∞Определение. Интерполяционный многочлен Лагранжа сходится равномерно к функции f (x)n→∞на отрезке [a; b], если max |Ln (x) − f (x)| −→ 0.x∈[a; b]Пример 4.1.Рассмотрим функцию f (x) = |x| на отрезке [−1; 1]. Будем брать равномерные разбиения отрезкаxk (n) = ± nk , k = 0, n и строить на них интерполяционные многочлены Лагранжа.1 Впервыеисследованы П. Л. Чебышевым (1859) и Ш. Эрмитом (1864).Ш.
Эрмитом (1878).2 Предложена60Глава 4. ИНТЕРПОЛЯЦИЯ И ПРИБЛИЖЕНИЕ ФУНКЦИЙОказывается, что для любой точки x 6= ±1, 0 сходимость отсутствует:lim |Ln (x) − f (x)| 9 0.n→∞Следующие теоремы показывают, что однозначного ответа на наш вопрос не существует.Теорема 4.1 (Фабер). Какова бы ни была последовательность сеток Ωn , всегда существует такаянепрерывная функция f (x), заданная на отрезке [a; b], что последовательность многочленов Лагранжа, построенная для каждой из этих сеток, не сходится равномерно к функции f (x) на отрезке[a; b].Теорема 4.2 (Марцинкевич). Пусть f (x) — непрерывная на отрезке [a; b] функция, тогда существует последовательность сеток Ωn такая, что соответствующая последовательность многочленовЛагранжа сходится равномерно к функции f (x) на отрезке [a; b].Обе этих теоремы мы принимаем без доказательства.Таким образом, у нас сложилась следующая ситуация.
При построении последовательности сеток,увеличивая степень многочлена:1) мы не гарантируем, что на выбранных узлах будет сходимость;2) создаются условия для накопления погрешности вычислений.Поэтому, если требуется построить интерполянту для большого отрезка [a; b], то делят этот отрезок на частичные сегменты, вводят небольшое число интерполяционных узлов на каждом сегменте истроят многочлены небольших степеней.
Эта процедура носит название кусочно-полиномиальнойинтерполяции.Если при выборе степени интерполяционного полинома на каком-нибудь отрезке его степень mпревосходит Nk − 1, то для однозначного построения не хватает данных, и нам требуется задатьдополнительные условия. Можно, например, на границе частичных отрезков потребовать непрерывности интерполянт и нужного числа их производных. Эта процедура называется интерполированиесплайнами.Но полином может иметь степень m меньше Nk − 1, тогда задача с условиями совпадения интерполянты с табличными значениями неразрешима, и поэтому следует отказаться от требования совпадения, а минимизировать функционал некоторого приближения к функции, например:sup |Hm (x) − f (x)| −→ inf .x∈[a; b]4.1Интерполирование кубическими сплайнамиРассмотрим задачу интерполирования функции f (x) на отрезке [a; b].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
