1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 78
Текст из файла (страница 78)
Рассматривая полином с переменной (−x) можно с помощьюэтого же результата найти число отрицательных корней исходного полинома.4.4бМетод дихотомииЭтот метод часто называют также методом бисекции или методомполовинного деления. Он заключается в последовательном делении пополам интервала локализации корня уравнения, на концах которогофункция принимает значения разных знаков. Теоретической основойметода дихотомии является следующий факт, хорошо известный в математическом анализе:4784. Решение нелинейных уравнений и их системТеорема 4.4.2 (теорема Больцано-Коши) Если функция f : R → Rнепрерывна на интервале X ⊂ R и на его концах принимает значенияразных знаков, то внутри интервала X существует нуль функцииf , т.
е. точка x̃ ∈ X, в которой f (x̃) = 0.Часто её называют просто «теоремой Больцано» (см., к примеру,[38]), так как именно Б. Больцано первым обнаружил это замечательное свойство непрерывных функций.Очевидно, что из двух половин интервала, на котором функция меняет знак, хотя бы на одной эта перемена знака обязана сохраняться.Её мы и оставляем в результате очередной итерации метода дихотомии.Рис. 4.8. Иллюстрация метода дихотомии (деления пополам)На вход алгоритму подаются функция f , принимающая на концахинтервала [a, b] значения разных знаков, и точность ǫ, с которой необходимо локализовать решение уравнения f (x) = 0.
На выходе получаеминтервал [x, x] шириной не более ǫ, содержащий решение уравнения.Недостаток этого простейшего варианта метода дихотомии — возможность потери решений для функций, аналогичных изображеннойна Рис. 4.8. На левой половине исходного интервала функция знакане меняет, но там находятся два нуля функции. Чтобы убедиться вединственности решения или в его отсутствии, можно привлекать дополнительную информацию об уравнении, к примеру, о производнойфигурирующей в нём функции. В общем случае потери нулей можноизбежать, если не отбрасывать подынтервалы, на которых доказательно не установлено отсутствие решений. Последовательная реализация4.4. Классические методы решения уравнений479Таблица 4.1. Метод дихотомии решения уравненийx ← a;x ← b;DO WHILE (x − x > ǫ)y ← 12 (x + x) ;IF f (x) < 0 и f (y) > 0 или f (x) > 0 и f (y) < 0x←yELSEx←yEND IFEND DOэтой идеи приводит к «методу ветвлений и отсечений», который подробно рассматривается далее в §4.8.Многомерное обобщение теоремы Больцано-Коши было опубликовано более чем столетием позже в заметке [44]:Теорема 4.4.3 (теорема Миранды) Пусть f : Rn → Rn , f (x) = f1 (x),⊤f2 (x), .
. . , fn (x) — функция, непрерывная на брусе X ⊂ Rn со сторонами, параллельными координатным осям, и для любого i = 1, 2, . . . , nимеет место либоfi X 1 , . . . , X i−1 , X i , X i+1 , . . . , X n ≤ 0илибоfi X 1 , . . . , X i−1 , X i , X i+1 , . . . , X n ≥ 0,fi X 1 , .
. . , X i−1 , X i , X i+1 , . . . , X n ≥ 0иfi X 1 , . . . , X i−1 , X i , X i+1 , . . . , X n ≤ 0,т. е. области значений каждой компоненты функции f (x) на соответствующих противоположных гранях бруса X имеют разные знаки. Тогда на брусе X существует нуль функции f , т. е. точка x⋆ ∈ X,в которой f (x⋆ ) = 0.4804. Решение нелинейных уравнений и их системХарактерной особенностью теоремы Миранды является специальная форма множества, на котором утверждается существование нуля функции: оно должно быть брусом со сторонами, параллельнымикоординатным осям, т. е. интервальным вектором. Для полноценногоприменения теоремы Миранды нужно уметь находить или как-то оценивать области значений функций на таких брусах.Удобное средство для решения этой задачи предоставляют методы интервального анализа.
Задача об определении области значенийфункции на брусах из области её определения эквивалентна задаче оптимизации, но в интервальном анализе она принимает специфическуюформу задачи о вычислении так называемого интервального расширения функции (см. §1.6).4.4вМетод простой итерацииМетодом простой итерации обычно называют стационарный одношаговый итерационный процесс, который организуется после того,как исходное уравнение каким-либо способом приведено к равносильному рекуррентному виду x = Φ(x). Далее, после выбора некоторогоначального приближения x(0) , запускается итерационный процессx(k+1) ← Φ(x(k) ),k = 0, 1, 2, . . .При благоприятных обстоятельствах последовательность {x(k) } сходится, и её пределом является решение исходного уравнения.
Но в общем случае и характер сходимости, и вообще её наличие существеннозависят как от отображения Φ, так и от начального приближения крешению.Пример 4.4.2 Уравнение (4.11) из Примера 4.4 нетрудно привести крекуррентному видуlα = sin α,hгде l = 3.3 и h = 3. Далее, взяв в качестве начального приближения,например, α(0) = 1, через 50 итерацийlsin α(k) ,k = 0, 1, 2, . . . ,(4.12)hполучаем пять верных знаков точного решения α∗ = 0.748986642697 . . .(читатель легко может самостоятельно проверить все числовые данныеэтого примера с помощью любой системы компьютерной математики).α(k+1) ←4.4.
Классические методы решения уравнений481Итерационный процесс (4.12) сходится к решению α∗ не из любогоначального приближения. Если α(0) = πl, l ∈ Z, то выполнение итераций (4.12) с идельной точностью даёт α(k) = 0, k = 1, 2, . . .. Если же α(0)таково, что синус от него отрицателен, то итерации (4.12) сходятся крешению (−α∗ ) уравнения (4.11). И нулевое, и отрицательное решенияочевидно не имеют содержательного смысла.С другой стороны, переписывание исходного уравнения (4.12) в другом рекуррентном виде —α=1arcsin(αh)l— приводит к тому, что характер сходимости метода простой итерациисовершенно меняется.
Из любого начального приближения, меньшегопо модулю чем примерно 0.226965, итерацииα(k+1) ←1arcsin α(k) h ,lk = 0, 1, 2, . . . ,сходятся лишь к нулевому решению. Бо́льшие по модулю начальныеприближения быстро выводят за границы области определения вещественного арксинуса, переводя итерации в комплексную плоскость, гдеони снова сходятся к нулевому решению. Таким образом, искомого решения α∗ мы при этом никак не получаем.Рассмотренный пример хорошо иллюстрирует различный характернеподвижных точек отображений и мотивирует следующие определения.Неподвижная точка x⋆ функции Φ(x) называется притягивающей,если существует такая окрестность Ω точки x⋆ , что итерационный процесс x(k+1) ← Φ(x(k) ) сходится к x⋆ из любого начального приближенияx(0) ∈ Ω.Неподвижная точка x⋆ функции Φ(x) называется отталкивающей,если существует такая окрестность Ω точки x⋆ , что итерационный процесс x(k+1) ← Φ(x(k) ) не сходится к x⋆ при любом начальном приближении x(0) ∈ Ω.Ясно, что простые итерации x(k+1) ← Φ(x(k) ) непригодны для нахождения отталкивающих неподвижных точек.
Здесь возникает интересный вопрос о том, какими преобразованиями уравнений и системуравнений отталкивающие точки можно сделать притягивающими.4824. Решение нелинейных уравнений и их системНаиболее часто существование притягивающих неподвижных точекможно гарантировать у отображений, которые удовлетворяют тем илииным дополнительным условиям, и самыми популярными из них являются так называемые условия сжимаемости (сжатия) образа.Напомним, что отображение g : X → X метрического пространстваX с расстоянием dist : X → R+ называется сжимающим (или простосжатием), если существует такая положительная постоянная α < 1,что для любой пары элементов x, y ∈ X имеет место неравенствоdist g(x), g(y) ≤ α · dist (x, y).Теорема 4.4.4 (теорема Банаха о неподвижной точке). Сжимающееотображение g : X → X полного метрического пространства X всебя имеет единственную неподвижную точку.
Она может бытьнайдена методом последовательных приближенийx(k+1) ← g(x(k) ),k = 0, 1, 2, . . . ,(0)при любом начальном приближении x∈ X.Доказательство этого результата можно найти, к примеру, в [17].Особенно ценен в теореме Банаха её конструктивный характер, позволяющий организовать численные методы для нахождения неподвижной точки.Иногда бывает полезно работать с векторнозначным расстоянием —мультиметрикой, — которая вводится на Rn какdist (x1 , y1 ).. ∈ Rn+ .Dist (x, y) := (4.13).dist (xn , yn )Для мультиметрических пространств аналогом теоремы Банаха онеподвижной точке для сжимающих отображений является приводимая ниже теорема Шрёдера о неподвижной точке.
Перед тем, как датьеё точную формулировку, введёмОпределение 4.4.1 Отображение g : X → X мультиметрического пространства X с мультиметрикой Dist : X → Rn+ называетсяP -сжимающим (или просто P -сжатием), если существует неотрицательная n × n-матрица P со спектральным радиусом ρ(P ) < 1, такаячто для всех x, y ∈ X имеет местоDist g(x), g(y) ≤ P · Dist (x, y).(4.14)4.4. Классические методы решения уравнений483Следует отметить, что математики, к сожалению, не придерживаются здесь единой терминологии.
Ряд авторов (см. [46]) за матрицей Pиз (4.14) закрепляют отдельное понятие «оператора Липшица (матрицы Липшица) отображения g», и в условиях Определения 4.4.1 говорят,что «оператор Липшица для g сжимающий».Теорема 4.4.5 (теорема Шрёдера о неподвижной точке) Пусть отображение g : Rn ⊇ X → Rn является P -сжимающим на замкнутомподмножестве X пространства Rn с мультиметрикой Dist . Тогдадля любого x(0) последовательность итерацийx(k+1) = g( x(k) ),k = 0, 1, 2, .
. . ,сходится к единственной неподвижной точке x∗ отображения g в Xи имеет место оценкаDist ( x(k) , x∗ ) ≤ (I − P )−1 P · Dist ( x(k) , x(k−1) ).Доказательство можно найти, например, в книгах [1, 18, 27, 46]4.4гМетод Ньютона и его модификацииПредположим, что для уравнения f (x) = 0 с вещественнозначнойфункцией f известно некоторое приближение x̃ к решению x∗ . Если f— плавно меняющаяся (гладкая функция), то естественно приблизитьеё в окрестности точки x̃ линейной функцией, т. е.f (x) ≈ f (x̃) + f ′ (x̃) (x − x̃),и далее для вычисления следующего приближения к x∗ решать линейное уравнениеf (x̃) + f ′ (x̃) (x − x̃) = 0.Отсюда очередное приближение к решениюx = x̃ −f (x̃).f ′ (x̃)Итерационный процессx(k+1) ← x(k) −f (x(k) ),f ′ (x(k) )k = 0, 1, 2, .
. . ,4844. Решение нелинейных уравнений и их системназывают методом Ньютона. Он явялется одним из наиболее популярных и наиболее эффективных численных методов решения уравнений и имеет многочисленные обобщения, в том числе на многомерныйслучай, т. е. в применении к решению систем уравнений (см. 4.7в).Пример 4.4.3 Рассмотрим уравнение x2 − a = 0, решением которого является квадратный корень из числа a. Если f (x) = x2 − a, тоf ′ (x) = 2x, так что в методе Ньютона для нахождения решения рассматриваемого уравнения имеем(k+1)x(k)= x2x(k) − af (x(k) )ax(k)(k)− ′ (k) = x −+ (k) .=2f (x )2x(k)2xИтерационный процесс для нахождения квадратного корняx(k+1) ←a 1 (k)x + (k) ,2xk = 0, 1, 2, . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
