Н.И. Ионкин - Численные методы (1163659), страница 12
Текст из файла (страница 12)
Как вычислять интегралы для поиска скалярных произведений функций для построения системы (3)?3. Как производить суммирование с коэффициентами Фурье?На первый из этих вопросов мы ответили в главе I, второго коснулись в§6, рассмотрение остальных вопросов выходит за рамки нашего курса.§8. Наилучшее среднеквадратичное приближение функций, заданных таблично§891Наилучшее среднеквадратичное приближениефункций, заданных табличноПусть — линейное пространство функций, заданных таблично, то есть элементы ∈ — функции, заданные в узлах 6 0 < 1 < .
. . < 6 , ∈ N: ( ) = , = 0, .Введем скалярное произведение в пространстве H:∀, ∈ (, ) =∑︁ .=0Введем соответствующую норму — эта норма является аналогом среднеквадратичной нормы в пространстве функций, определенных на всем отрезке[, ]:(︃ )︃1/2∑︁√︀2∀ ∈ ‖ ‖ = (, ) =.=0В предыдущем параграфе предполагалось, что функция () задана аналитически. Здесь функция задана таблично, то есть известны только ее значения = ( ) в конечном числе точек , = 0, .Мы хотим приблизить функцию () некоторой функцией, заданной аналитически.
Один из способов приближения мы уже знаем — это интерполяция по данным значениям 0 , 1 , . . . , . Однако при больших такой способприближения трудоемок и может даже дать неверное представление о поведении функции. Одним из распространенных способов приближения функций,заданных таблично, является способ, основанный на минимизации среднеквадратичной погрешности.Как и в предыдущем параграфе, предположим, что задана система базисных функций { ()}=0 (например, () = , = 0, ).
Можем считать, чтофункции () заданы только в точках , = 0, . Задача состоит в подборекоэффициентов , для которых величина отклонения⃒⃒ ⎛⃒⃒(︃)︃2 ⎞1/2⃒⃒⃒⃒∑︁∑︁∑︁⃒⃒⃒⃒ ⃒⃒ = ⎝ − ( ) ⎠⃒⃒ −⃒⃒⃒⃒=0=0=0являлась бы минимальной. Эта задача является дискретным аналогом задачио минимизации функционала (0 , 1 , . . . , ), рассмотренной в предыдущемпараграфе, и решается аналогичным образом.92Глава II .
Интерполирование и приближение функцийВведем функционал⃒⃒⃒⃒2⃒⃒⃒⃒∑︁⃒⃒⃒⃒ (0 , 1 , . . . , ) = ⃒⃒ − ⃒⃒ .⃒⃒⃒⃒=0Этот функционал имеет тот же вид, что и аналогичный функционал дляфункций гильбертового пространства, рассмотренный в предыдущем параграфе.Запишем систему линейных уравнений для поиска коэффициентов { }=0 ,на которых функционал (0 , 1 , . . . , ) достигает своего минимума:= 0,∑︁ = 0, , ( , ) = (, ), = 0, .=0Вид полученной системы аналогичен виду системы, которую мы рассматривали в предыдущем параграфе, следовательно, для рассматриваемой системысохраняется свойство существования и единственности решения — { }=0 .Значит, для построения наилучшего среднеквадратичного приближенияфункции с помощью некоторой системы функций достаточно знать значенияэтой функции лишь в некоторых точках интересующего отрезка.Глава IIIЧисленное решениенелинейных уравнений исистем нелинейных уравнений§1Способы локалзации корней нелинейного уравненияРассмотрим задачу поиска корней нелинейного уравнения: нелинейные уравнения, вообще говоря, не имеют аналитического решения, поэтому для поискарешения используют вычислительные методы, хотя такое решение являетсялишь приближенным.Заметим, что принципиальное отличие численных методов решения нелинейных уравнений от численных методов решения систем линейных уравнений состоит в необходимости специально выбирать для конкретного итерационного метода начальное приближение, так как от этого выбора зависит сходимость рассматриваемых итерационных методов решения нелинейных уравнений.Постановка задачи.Рассмотрим функцию (), ∈ R, и уравнение () = 0.(1)Пусть * — вещественный корень уравнения, и определена его окрестностьрадиуса , не содержащая других корней уравнения: (* ) = { : | − * | < },94Глава III .
Численное решение нелинейных уравнений и систем нелинейных уравненийпричем заданная функция () определена на этой окрестности. Будем считать, что начальное приближение 0 ∈ (* ) задано. Тогда для нахождения численного решения уравнения в рассматриваемой окрестности необходимо построить последовательность { }, сходящуюся к корню * уравнения (1):lim ( ) = (* ) = 0.→∞Численное решение нелинейных уравнений можно разбить на два этапа:1. Локализация корня, т.е. определение окрестности (* ).2. Задание итерационного процесса — построение последовательности { },сходящейся к корню уравнения.Пусть () — непрерывная функция, заданная на отрезке [, ]. Рассмотрим два приема локализации вещественного корня (известно, что уравнение(1) может иметь и комплексные корни, но в данном курсе мы не будем имизаниматься).Первый приемПусть задано разбиение сегмента [, ]: 6 0 < 1 < 2 < .
. . < 6 ,и если для некоторого = 1, выполняется условие (−1 ) ( ) < 0,(2)то на интервале (−1 , ) существует по крайней мере один корень уравнения (1) или число корней на этом интервале нечетно. Если же выполняетсяусловие (−1 ) ( ) > 0, = 1, ,то на каждом из интервалов (−1 , ) либо нет корней уравнения (1), либоих число четно.В случае выполнения условия (2) интервал (−1 , ) вновь разбиваетсяна частичные интервалы, и для частичных интервалов повторяется описанная выше процедура, которая в итоге позволит найти промежуток меньшейдлины, содержащий корень.§1.
Способы локалзации корней нелинейного уравнения95Второй приемБолее регулярным способом отделения действительных корней является метод бисекции (деления пополам).Предположим, что на интервале (, ) расположен лишь один корень *уравнения (1). Тогда () и () имеют различные знаки. Пусть для определенности () > 0, () < 0.Положим+0 =2и рассмотрим значения функции () в этой точке.Если (0 ) < 0, то значение искомого корня * лежит в интервале (, 0 ),если же (0 ) > 0, то * ∈ (0 , ).
Далее из этих двух интервалов (, 0 )и (0 , ) выбираем тот, на границе которого функция () имеет различныезнаки.Затем находим точку 1 — середину выбранного интервала, вычисляем (1 )и повторяем указанный выше алгоритм.В результате получаем последовательность интервалов, содержащих искомый корень * , причем каждый последующий интервал имеет длину в 2раза меньшую, чем предыдущий. Процесс заканчивается, когда длина вновьполученного интервала станет меньше заданного числа > 0.Как правило рассматриваемая функция () имеет больше одного корня, и задача состоит в поиске всех корней уравнения (1) на областиопределения функции (). Тогда можно поступать следующим образом:пусть мы нашли один из корней = * этого уравнения, причем этоткорень имеет единичную кратность.
Тогда для поиска других корней рассматриваемого уравнения осуществим переход к функции () видаЗамечание.() = (). − *Очевидно, что уравнение () = 0 имеет на единицу меньше корней, чемуравнение (1), и все корни этого уравнения являются также корнями уравнения (1). Поэтому после решения данного уравнения получаем корни исходного уравнения, отличные от уже найденных. Таким образом мы сможемнайти по крайней мере все некратные корни уравнения (1).Круг вопросов, которые мы рассматриваем в связи с решением одногонелинейного уравнения, переносится и на поиск решения системы нелинейных уравнений. Рассмотрим нелинейную систему уравнений (1 , 2 , .
. . , ) = 0, = 1, .(3)96Глава III . Численное решение нелинейных уравнений и систем нелинейных уравненийВведем векторы = (1 , 2 , . . . , ) , = (1 , 2 , . . . , ) . Тогда системауравнений (3) запишется в векторной форме, как () = .Последнее уравнение удобно рассматривать как операторное уравнение в мерном пространстве R . При этом отображение : R −→ Rпредставляет собой нелинейное отображение пространства R в себя, и рассуждения о методах решения нелинейных систем проводится аналогично одномерному случаю.§2Метод простой итерацииРассмотрим функцию (), ∈ R и уравнение(1) () = 0.Пусть * — вещественный корень этого уравнения, и определена его окрестность радиуса , не содержащая других корней рассматриваемого уравнения: (* ) = { : | − * | < },причем заданная функция () определена на этой окрестности.Будем считать, что начальное приближение 0 ∈ (* ) задано.
Рассмотрим итерационные методы, задаваемые общей формулой+1 = ( ), ∈ Z+(2)с некоторой функцией (), определенной на (* ). Пусть функция ()имеет вид() = + () (), (* ) = * ,(3)где () — функция, не обращающаяся в ноль в окрестности (* ), то есть(()) ̸= 0, ∈ (* ).Итерационный метод, описываемый формулой (2) с функцией () вида (3), называется методом простой итерации.Определение.Функция () удовлетворяет условию Липшица при ∈ (* ) с константой > 0, если для любых точек 1 , 2 ∈ (* ) выполненонеравенство|(1 ) − (2 )| 6 |1 − 2 |.Определение.§2. Метод простой итерации97Пусть функция () удовлетворяет условию Липшица сконстантой ∈ (0, 1) в некоторой окрестности (* ), и пусть заданоначальное приближение 0 ∈ (* ).
Тогда метод простой итерации (2)сходится со скоростью геометрической прогрессии со знаменателем .Утверждение.Докажем с помощью метода математической индукции,что ∈ (* ) при ∈ Z+ .Справедливость утверждения 0 ∈ (* ) следует из условия. Пусть требуемое условие верно при = . Рассмотрим ( + 1)-ю итерацию:Доказательство.+1 = ( )и оценим |+1 − * |, учитывая, что функция () удовлетворяет условиюЛипшица:|+1 − * | = |( ) − (* )| 6 | − * |.(4)Из условия ∈ (0, 1) следует неравенство|+1 − * | 6 | − * | < .Таким образом, +1 ∈ (* ).Докажем сходимость метода простой итерации. Используя оценку (4) какрекуррентную, получим:| − * | 6 |0 − * |.(5)Из условия ∈ (0, 1) следует, чтоlim = 0.→∞Тогда из неравенства (5) получимlim | − * | = 0.→∞Следовательно, метод простой итерации сходится со скоростью геометрической прогрессии со знаменателем .Если функция () непрерывно дифференцируема, то в качестве можно взять максимальное значение | ′ ()|, и сходимость будетиметь место, еслиЗамечание.=⃒⃒max ⃒ ′ ()⃒ < 1.∈ (* )98Глава III .
Численное решение нелинейных уравнений и систем нелинейных уравненийРассмотрим итерационный метод, записанный равенством:+1 − + ( ) = 0, ∈ R+ , ∈ Z+ , 0 ∈ (* ).(6)Выразим из этого равенства +1 :+1 = − ( ).Этот метод является методом простой итерации вида (2) с функцией (),имеющий вид() = − ().Получим оценку параметра , которая будет гарантировать сходимостьметода простой итерации вида (6), то есть обеспечивать выполнение условийзамечания к доказанному выше утверждению.Пусть окрестность (* ) выбрана таким образом, чтобы в ней выполнялось условие | ′ ()| < 1. В предположении об ограниченности функции ′ ()вычислим точную верхнюю грань ее модуля:⃒⃒ = sup ⃒ ′ ()⃒ .∈ (* )Продифференцируем функцию (): ′ () = 1 − ′ ().Пусть для определенности ′ () > 0, ∈ (* ).
Потребовав, чтобы выполнялось условие | ′ ()| < 1, получим оценку для :|1 − | < 1,0< <2.Таким образом, если для поиска корня * применяется итерационный метод,записанный в виде (6) и ′ () (︀> 0, )︀ ∈ (* ), то значение параметра 2.следует выбирать из интервала 0, Метод Эйткена ускорения сходимости итерационного методаВ связи с методом простой итерации остановимся на одном приеме ускоренияскорости сходимости, который называется методом Эйткена.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
