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

21

Пусть P(z) = 0 можно представить в виде

P(z) = Q(z) + ε(z), где ε(z) << Q(z)

Q(z) известны. Тогда корни P(z)

0,001x3 + x2 − 5x + 6 = 0

Обозначив Q(x) = x2 − 5x + 6,ε(x) = 0,001x3 , получим (как следует из анализа рисунка 2.2) небольшой сдвиг корней.

2.2.2. Вычисление значений корня с заданной точностью. Метод итераций

Будем считать, что первая задача (задача отделения корней) решена, т.е. выделена область, в которой P(z) = 0. Требуется найти в ней корень с любой точностью. Уравнение преобразуем к виду

В выделенной области назначим приближение z0 – нулевое приближение корня. Следующие приближения корня находим так:

1) для любых двух точек z' и z' ' , находящихся в области| z − z0 |≤δ, имеет место неравенство

| ϕ(z' ) −ϕ(z' ' ) |≤ q | z'−z' '|,

22

где q – вещественное число из интервала (0,1); 2) имеет место неравенство

Тогда последовательность приближенных значений корня {zn } сходится, и предел

последовательности принадлежит заданной области отделения корня. Кроме того, скорость сходимости определяется следующим неравенством:

Доказательство

Формально доказательство сводится к доказательству справедливости следующей формулы:

| zk − zk −1 |≤ mq k −1 для любого k =1,2,....

Проведем доказательство по индукции.

1. База индукции. Покажем, что формула справедлива при k =1: | z1 − z0 |=| ϕ(z0 ) − z0 |= m.

Итак, решение единственно. Обсудим условия теоремы.

При | z − z0 |≤δ | ϕ(z' ) −ϕ(z' ' ) |≤ q | z'−z' '| .

23

Это условие называется условием Липшица. Оно является более широким, чем условие дифференцируемости функций, т.е. функции, имеющие производную, входят в класс функций, удовлетворяющих условию Липшица. Если функция дифференцируема и ее производная ≤ q, то

она удовлетворяет условию Липшица. Действительно, применяя формулу Тейлора, можно записать

ϕ(z' ) −ϕ(z' ' ) =ϕ'[z'+Θ(z' '−z' )](z' '−z' ),0 < Θ <1,

или, переходя к модулю в левой и правой частях, и, обозначая максимум модуля производной через q, получаем условие Липшица.

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

двумя соседними значениями xk , xk +1 .

На рисунке 2.5 продемонстрировано, каким образом сказывается невыполнение условия Липшица.

24

Обсудим второе условие теоремы. Оно говорит о том, что разность | ϕ(x0 ) − x0 | не может быть сколь угодно велика: она ограничена величиной δ(1 − q). Скорость сходимости существенно зависит от величины q, что иллюстрируется следующими рисунками.

При q ≈ 0 итерационный процесс сходится к значению корня x* очень быстро, при q ≈1

– медленно.

2.2.3. Метод итераций для системы уравнений

Рассмотрим итерационный метод для решения системы k уравнений с k неизвестными:

26

2.2.4. Принцип сжатых отображений

Пусть R – полное метрическое пространство и пусть для всех элементов этого пространства определен оператор А "в себя" (результат действия этого оператора – отображение элементов в элементы того же пространства). Тогда говорят, что оператор А осуществляет сжатое отображение, если для любых двух элементов x', x'' этого пространства и любого действительного числа 0<q<1 имеет место неравенство

ρ(Ax', Ax' ' ) ≤ qρ(x', x' ' ),

т.е. образы элементов ближе, чем их прообразы. В таких случаях говорят, что оператор А сжимает. Теорема. Пусть в полном метрическом пространстве R оператор А осуществляет сжатие отображения "в себя". Тогда оператор А имеет единственную неподвижную точку, т.е. уравнение Ax=x имеет единственное решение, которое может быть получено как предел последовательности

итераций вида xn = Axn−1 (Точка является неподвижной для оператора, если он переводит ее саму

в себя).

Доказательство

Покажем, что последовательность значений {xn }∞n=0 , полученная итерированием,

последовательность неравенств:

ρ(xn , xm ) = ρ(Axn−1, Axm−1 ) ≤ qρ(xn−1, xm−1),

ρ(xn−1, xm−1 ) ≤ qρ(xn−2 , xm−2 ),

………………………………

ρ(xn−m+1, x1) ≤ qρ(xn−m , x0 ).

Перемножив эти неравенства, получим

ρ(xn , xm ) ≤ qm ρ(xn−m , x0 ).

Оценим ρ(xn−m , x0 ), применив n-m раз правило треугольника:

ρ(xn−m , x0 ) ≤ ρ(xn−m , xn−m−1 ) + ρ(xn−m−1, xn−m−2 ) +... + ρ(x1, x0 ) ≤

≤(qn−m−1 +... + q2 + q +1)ρ(x1, x0 ) < ρ1(x−1,qx0 ) .

Окончательно получаем

ρ(xn , xm ) ≤ 1q−mq ρ(x1, x0 ),

т.е. при n>m критерий Коши доказан: ρ(xn , xm ) →0. В силу полноты пространства R (для

n,m→∞

любой последовательности в пространстве R, сходящейся в себе, найдется предельный элемент,

значит – неподвижная точка оператора. Покажем, что эта точка единственная. Проведем доказательство от противного. Предположим, что существует еще одна неподвижная точка x'≠ x* и Ax’=x’. Поскольку ρ(x* , x') = ρ(Ax* , Ax') ≤ qρ(x*, x'), а q<1, то получили противоречие, т.е. x’ не может быть неподвижной точкой.

27

2.2.5. Об одном принципе нахождения сходящихся итерационных процессов

Пусть имеется уравнение f (x) = 0, где x – действительная переменная и пусть на [a,b] отделен единственный корень x* этого уравнения. Пусть на этом сегменте задана некоторая непрерывная функция ψ(x). Тогда уравнение вида x = x −ψ(x) f (x) также имеет корень x*.

Принцип получения сходящихся итерационных процессов состоит в следующем. Нужно уметь так подобрать непрерывную функцию ψ(x), чтобы получившееся уравнение x = ϕ(x), где

ϕ(x) = x −ψ(x), давало сходящийся итерационный процесс.

2.2.6. Метод хорд (секущих) и метод деления пополам

Данный метод является одним из методов, реализующих принцип получения сходящегося итерационного процесса. Пусть единственный корень x* уравнения f (x) = 0 отделен на [a,b].

Предположим, что f (x) изменяется на [a,b] монотонно.

Заменим кривую y = f (x) хордой, проходящей через точки (a, f (a)) и (b, f (b)). В качестве первого приближения корня уравнения f (x) = 0 возьмем точку пересечения этой хорды

28

| xn − x* |≤ f (xn ) / m.

Формула тем точнее, чем меньше сегмент [a,b] отделения корня.

Из геометрии задачи вытекает, что первое приближение значения корня x1 делит сегмент [a,b] в соответствии со следующим соотношением:

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

29

2.2.7. Метод Ньютона (метод касательных)

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

Пусть некоторое значение x0 (a, b). Заменим f(x) некоторой линейной функцией, используя

формулу Лагранжа:

f (x) = f (x0 ) + f ' (ξ)(x − x0 ), где x <ξ < x0 x0 <ξ < x.

Поскольку значение ξ неизвестно, выберем в качестве ξ точку x0:

уравнением f(x0)+f'(x0)(x-x0)=0, корень которого примем за первое приближение значения корня уравнения f(x)=0:

Обобщая уравнение (10), получаем следующий итерационный процесс:

ψ(x) =1/ f ' (x) .

Сдругой стороны, уравнение (9) является уравнением касательной к кривой в точке x0. На каждом шаге итерационного процесса функция f(x) заменяется касательной к этой функции, проведенной в точке предыдущего приближенного значения корня. Из геометрии задачи вытекает,

что первую касательную удобно проводить с того конца сегмента, в котором выполняется условие f (x) f ' ' (x) > 0.

Теорема. Если функция f(x) имеет единственный корень на [a,b], непрерывные f'(x), f''(x), которые не меняют знака на этом сегменте, то если начинать итерационный процесс со значения

x0 [a, b], для которого выполняется условие f (x0 ) f ' ' (x0 ) > 0, то итерационный процесс

монотонно сходится к некоторому значению корня x*.

Рассмотрим упрощенный метод Ньютона. Он заключается в том, что итерационный процесс строится на основе следующей формулы:

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

30

2.2.8. Вычисление значений алгебраического полинома

Пусть задан алгебраический полином n-й степени с действительными коэффициентами

Требуется определить значение этого полинома в точке x0. Подсчитаем число операций, необходимых для решения этой задачи. Операций умножения: n+(n-1)+(n-2)+…+1=n(n+1)/2; операций сложения: n. Нельзя ли предложить метод, сокращающий число операций? Рациональный процесс подсчета значения многочлена основан на теореме Безу.

Теорема. Остаток от деления многочлена Pn (x) на двучлен (x-x0) равен значению

многочлена в точке x0.

Доказательство

Запишем результат деления Pn (x) на (x − x0 ) в виде суммы остатка от деления R и

Положим в этом выражении x=x0:

Pn (x0 ) = (x0 − x0 )Qn−1 (x0 ) + R = R. .

Подставив этот результат в (14), получим

Pn (x) = (x − x0 )(b0 x n−1 +b1 x n−2 +... +bn−2 x +bn−1 ) + R..

Выразим коэффициенты многочлена Qn-1 через коэффициенты Pn.

Теорема. Два многочлена тождественно равны тогда и только тогда, когда их коэффициенты при одинаковых степенях x совпадают.

Имеем:

Преобразование коэффициентов удобно представить в виде так называемой схемы Горнера (таблица 1).

Таблица 1

умножения и n действий сложения.