Н.И. Ионкин - Электронные лекции (2010) (1135227), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Наилучшее среднеквадратичное приближение существует и единственно.Доказательство. Рассмотрим сначала случай = 0:0 () ∈ 2 , () = 0 0 ()Введем функцию (0 ):2∫︁ (0 ) = || − ()|| =( () − ())2 =Наилучшее среднеквадратичное приближение функции∫︁= 2 () − 20∫︁51 ()0 () + 02∫︁20 () =02 (0 , 0 )= (, ) − 20 (, 0 ) +Необходимое условие минимума для функции F:=000Минимум этой функции по переменнойнаходится в вершине параболы:(, 0 )(0 , 0 )0 =Таким образом:() = 0 0 ()Рассмотрим пример. Пусть0 () = 1,тогда:∫︀ ()0 =∫︀1=−∫︁ ()1() =−∫︁ ()Получили среднее значение функции ()на[, ].Рассмотрим теперь общий случай.

Пусть задана система функций (1). Введем функцию (0 , 1 , . . . , ):)︃2∫︁ (︃∑︁ (0 , 1 , . . . , ) = || − ()|| = () − () =2=0∫︁2 () − 2=∑︁∫︁=0= (, ) − 2 ()0 () +=0∑︁∑︁ (, ) +=0∑︁∫︁=0∑︁=0∑︁20 () = ( , )=0Запишем необходимое условие минимума для функции F: (0 , 1 , . . . , )= 0, = 0, 1, . . . , Тогда получим систему уравнений для нахождения коэффициентов∑︁=0 ( , ) = (, ), = 0, 1, .

. . , (3)Наилучшее среднеквадратичное приближение функции52Матрицей этой системы является матрица Грама:⎛⎞(0 , 0 ) (0 , 1 ) · · · (0 , )⎜ (1 , 0 ) (1 , 1 ) · · · (1 , ) ⎟⎜⎟ = ⎜ ..⎟......⎝ .⎠...(0 , ) (1 , ) · · · ( , )Так как система функций (1) линейно независима, то определитель Грама ̸= 0,а значитнаилучшее среднеквадратичное приближение существует и единственно (можно однозначнонайти коэффициенты ).Замечание. Если система функций(, )(1) - ортонормированная, то есть( , ) = ,то =- коэффициенты Фурье.Замечание. Пусть задана система функций:1, , 2 . . . , Пусть() > 0- весовая функция.∫︁() () () = 0ВыбираяПусть(), , { }0 -можно получить ортогональные многочлены.ортонормированная система.

Тогда наименьшее отклонение:∫︁ (︃0≤ () −∫︁∑︁)︃2 () ==0 2 () − 2∑︁ ( , ) +=0(, ) −∑︁2 ==0∑︁2 ≥ 0=0Таким образом, мы получили неравенсвто Бесселя:∑︁2 ≤ || ||2=0Если система{ }0– ортонормированный базис, иБесселя станет равенством Парсеваля:2|| || =∞∑︁=02( , ) = ,то полученное неравенствоГлава IIIЧисленное решение нелинейныхуравнений и систем нелинейныхуравнений§1ВведениеПусть задана функция (), ∈ R, причем[, ]функция f непрерывна.Будем решать уравнение на отрезке () = 0, ∈ [, ]Процесс решения разбивают на 2 этапа:1.

Локализуем корни (при этом корни могут быть комплексные)2. Строим итерационный метод нахождения корняОпределение. a-окрестностью корня * называется множество точек (* ) = { : | − * | ≤ }Рассмотрим способы локализации корня:1. Разобьем отрезок[, ]множеством точек{ }1 ≤ 0 < 1 < . . . < ≤ (−1 ) ( ) < 0, то на отрезке [−1 .. ] есть по крайнейможет быть нечетное число). Если же (−1 ) ( ) > 0, тоТогда можно утверждать, что еслимере один корень (также ихсказать ничего нельзя, так как на этом отрезке либо четное число корней, либо корней нетвообще.2.

Метод бисекции (деления пополам) Пусть () ∈ [, ]; () < 0, () > 0Возьмем0 =+.253Метод простой итерацииЕслиЕслиЕсли54 (0 ) > 0, то корень уравнения * ∈ (, 0 ) (0 ) < 0 , то корень уравнения * ∈ (0 , ) (0 ) = 0, то мы нашли корень уравнения.+0, во втором2локализации корня, и так далее.В первом случае возьмем1 =1 =0 +, и аналогично повотрим процедуру2В случае, если дана система уравнений⎧⎪⎨1 (1 , . . . , ) = 0,...⎪⎩ (1 , .

. . , ) = 0,ее можно представить в виде§2⃗(⃗) = 0,где⃗ = (1 , 2 , . . . , ) , ⃗ = (1 , 2 , . . . , )Метод простой итерацииИтак, мы решаем уравнение () = 0*- корень уравнения, локализованный на(1) (* )Заменим уравнение на эквивалентноегде функция() = ()(2)() = + () ()(3)не меняет знак наПостроим последовательность{ } (* )следующим образом:0 ∈ (* )+1 = ( ), = 0, 1, .

. .(4)Определение. Функция S(x) Липшиц-непрерывна (удовлетворяет условию Липшица) с константойq >0, если|(1 ) − (2 )| ≤ |1 − 2 |, ∀1 , 2 ∈ (, )Утверждение. Если S(x) удовлетворяет условию Липшица с 0 < < 1 на (* ) и | − 0 | <,то метод простой итерации (4) решения уравнения (1) сходится, причем со скоростьюгеометрической прогрессии со знаменателем q.Доказательство.

По построению|0 − * | < ,значит|+1 − * | = |( ) − (* )| ≤ | − * | ⇒| − * | ≤ lim→∞ = 0,так как0 < < 1.Следовательно, метод сходится, причем со скоростью геометрической прогресси со знаменателемq.Метод Ньютона и метод секущих55Замечание. Если S(x) дифференцируема на (* ), то = sup∈ (* ) | ′ ()|Замечание. Пусть f(x) дифференцируема, ′ () > 0 на (* ) и ∃1 = sup∈ (* ) | ′ ()|Тогда запишем метод простой итерации в виде:+1 − + ( ) = 0,+1 = ( ), >0() = − ()∃ ′ () = 1 − ′ () на (* ). Для = sup∈ (* ) |1 − ′ ()| < 1, т.е.

чтобы 0 < < 21Следовательно,сходимости метода необходимо, чтобыМетод Эйткена (ускорение сходимости)Метод Эйткена не является теоретически обоснованным, но при приближенных значенияхпараметров позволяяет увеличить скорость сходимости.Пусть − * ≃ , где A и q - некоторые константы. Тогда:−1 − * = −1 − * = +1 − * = +1следовательно,(+1 − )2 = 2 2 ( − 1)2(+1 − 2 + −1 ) = −1 ( − 1)2Откуда получаем:(+1 − )2= +1 = +1 − *+1 − 2 + −1Стало быть:* ≃ +1 −(+1 − )2+1 − 2 + −1Из-за неточности в качестве следующей итерации мы должны взять значение, близкое к§3*Метод Ньютона и метод секущихМы решаем уравнение () = 0Пусть корень локализован наРазложим (* ) (* ), () ∈ 1 ( (* )),(1)при этом ′ () ̸= 0напо Тейлору:0 = (* ) = () + ′ ()(* − ) + (* − ) ≈ () + ′ ()(* − )Положим в этой формуле = , * = +1 ,тогда получим:+1 = − ( ) ′ ( ) (* ).Метод Ньютона и метод секущихВзяв0 ∈ (* ),56получаем метод Ньютона:+1 = − ( ), = 0, 1, 2, .

. . ′ ( )На каждой итерации считать производную затратно, в то же время на небольшом интервалеона, как правило, меняется не сильно. Следовательно, можно использовать производную, одинраз вычисленную на первой итерации. Получаем модифицированный метод Ньютона:+1 = − ( ), = 0, 1, 2, . . .

; 0 ∈ (* ) ′ (0 )Модифицированный метод Ньютона сходится медленнее обычного метода Ньютона, но быстрееметода простой итерации.Метод Ньютона для системы уравненийРассмотрим систему:{︃1 (1 , 2 ) = 0,2 (1 , 2 ) = 0,Пусть(*1 , *2 )- ее решение. Разложим1и2(2)в окрестности корня:0 = 1 (*1 , *2 ) = 1 (1 , 2 ) +1 (1 , 2 ) *1 (1 , 2 ) *(1 − 1 ) +(2 − 2 ) + . . .120 = 2 (*1 , *2 ) = 2 (1 , 2 ) +2 (1 , 2 ) *2 (1 , 2 ) *(1 − 1 ) +(2 − 2 ) + . .

.12ЗаменяяОбозначимнаи*на+1,получим:1 (1 , 2 ) +1 (1 , 2 ) +11 (1 , 2 ) +1(1 − 1 ) +(2 − 2 ) = 0122 (1 , 2 ) +2 (1 , 2 ) +12 (1 , 2 ) +1(1 − 1 ) +(2 − 2 ) = 012 = (1 , 2 ) , = (1 , 2 ) ,[︃( ) =а также1 (1 ,2 )12 (1 ,2 )11 (1 ,2 )22 (1 ,2 )2]︃(3)Тогда уравнение можно записать в виде: ( ) + ( )(+1 − ) = 0Если∀ ∃ −1 ( ),(4)то+1 = − −1 ( ) ( ), = 0, 1, 2, . .

. ;0– задано(5)Метод Ньютона и метод секущих57Замечание. Считать −1 ( ) не очень удобно, поэтому обычно вводят погрешность +1 = +1 − и решают на каждой итерации уравнение:( ) +1 = − ( )Замечание. В случае системы можно применить модифицированный метод Ньютона:+1 = − −1 (0 ) ( )Но в этом случае скорость сходимости будет значительно меньше.Если дана система из m уравнений:⎧1 (1 , . . . , ) = 0,⎪⎪⎪⎨ ( , . . . , ) = 0,2 1⎪...⎪⎪⎩ (1 , . . . , ) = 0,то также можно использовать метод Ньютона, в этом случае( ) = ( ),, = 1, Система в этом случае имеет тот же вид: ( ) + ( )(+1 − ) = 0Метод секущихЗапишем метод Ньютона:+1 = −Заменим в нем ′ ( )на ( ), ′ ( )0 ∈ (* ), = 0, 1, 2, .

. . . ( )− (−1 ). −−1Получим+1 = − − −1 ( ) ( ) − (−1 )Поскольку в записи данного метода учавствуют три последовательные итерации ((6)+1, и −1 ),то он называется двухшаговым методом. Для того, чтобы воспользоваться им, требуется задать01два начальных приближения ( и ).

Их можно получить методом простой итерации илиметодом Ньютона.+1 при помощи интерполяции функции−1используя ее значение в узлах и .Заметим, что, используя метод секущих, мы получаемполиномом первой степени (линейной функцией),Сходимость метода Ньютона и оценка сходимости§458Сходимость метода Ньютона и оценка сходимостиРассматривается нелинейное уравнение () = 0.(1)Запишем для него метод Ньютона:+1 = − ( ), ′ ( ) = 0, 1, .

. . ;0 ∈ (* ).(2)Запишем это метод в более общем виде:+1 = ( ),Тогдагде() = − (). ′ ()( ′ ())2 − () ′′ () () ′′ () () = 1 −=.( ′ ())2( ′ ())2′ ′ (* ) = 0. = − * – погрешность.Заметим, чтоПустьТогда +1 = +1 − * = ( ) − (* ) = ( + * ) − (* ).Воспользуемся формулой Тейлора с остаточным членом в форме Лагранжа:11 +1 = (* ) + ′ (* ) + ′′ (˜ )2 − (* ) = ′′ (˜ )2 ,22где˜ = + , || < 1.Пусть ∃ > 0 такое, что1 ′′| ()| ≤ ,2 ∈ (* ).(3)Тогда|+1 | ≤ | |2 , |+1 | ≤ ( | |)2 .Применим это неравенство рекурсивно, получим | | ≤ ( |0 |)2 ,1( |0 |)2 .| | → 0 ⇒ → * .| | ≤Если |0 | < 1,то при→∞получаемТаким образом, для сходимости данного метода достаточно потребовать1.(4)1( |0 − * |)2 .(5)|0 | = |0 − * | ≤Дляимеем оценку| | = | − * | ≤Мы доказали следующую теорему.Сходимость метода Ньютона и оценка сходимостиТеорема∃ > 0(обоценкетакое, чтоскорости59сходимости⃒(︂)︂′ ⃒1 ⃒⃒ () ′ () ⃒⃒≤2 ⃒ ( ′ ())2 ⃒|0 − * | ≤методаНьютона).Пусть∀ ∈ (* ),1.Тогда метод Ньютона сходится и имеет место оценка| − * | ≤1( |0 − * |)2 .Замечание.

Характеристики

Список файлов лекций