Приближённые методы решения алгебраического уравнения
Реферат по курсу
численных методов выполнил студент группы РЭ–01-1
Днепропетровский
Национальный Университет
Радиофизический
факультет
Кафедра физики
СВЧ
Днепропетровск
2002
1. Численное решение уравнений с одним неизвестным
В
данной работе рассматриваются метода приближённого вычисления действительных
корней алгебраического или трансцендентного уравнения
f(x)=0 (1.1)
на
заданном отрезке [a, b].
Уравнение
называется алгебраическим, если заданная функция есть полином n-ой степени:
f(x) = P(x) = a0xn
+ a1xn- 1 + … + an-1 x + an
= 0, a0 ¹ 0
Требование
a0 ¹ 0 обязательно, так как при
невыполнении этого условия данное уравнение будет на порядок ниже.
Всякое
уравнение (1.1) называется
трансцендентным, если в нём невозможно явным образом найти неизвестное, а можно
лишь приближённо.
Однако
в число алгебраических уравнений можно также включить те уравнения, которое
после некоторых преобразований, можно привести к алгебраическому.
Те
методы, которые здесь рассматриваются, применимы, как к алгебраическим
уравнениям, так и к трансцендентным.
Корнем
уравнения (1.1) называется такое
число x,
где f(x)=0.
При
определении приближённых корней уравнения (1.1) необходимо решить две задачи:
отделение
корней, т. е. определение достаточно малых промежутков, в каждом из которых заключён
один и только один корень уравнения (простой и кратный);
уточнение
корней с заданной точностью (верным числом знаков до или после запятой);
Первую
задачу можно решить, разбив данный промежуток на достаточно большое количество
промежутков, где бы уравнение имело ровно один корень: на концах промежутков
имело значения разных знаков. Там где данное условие не выполняется, те
промежутки откинуть.
Вторая
задача решается непосредственно в методах рассмотренных ниже.
При
графическом отделении корней уравнения (1.1) нужно последнее преобразовать к виду:
j1(x)=j2(x) (2.1)
и
построить графики функций y1=j1(x), y2=j2(x).
Действительно,
корнями уравнения (1.1)
f(x) = j1(x) - j2(x) = 0
являются
абсциссы точек пересечения этих графиков (и только они).
Из
всех способов, какими можно уравнение (1.1) преобразовать к виду (2.1) выбираем тот, который обеспечивает
наиболее простое построение графиков y1=j1(x) и y2=j2(x). В частности можно взять j2(x) = 0 и тогда придём к построению
графика функции (1.1), точки
пересечения которого с прямой y2=j2(x)=0, т. е. с осью абсцисс, и есть
искомые корни уравнения (1.0).
Условия,
наложенные на функцию f(x) на отрезке [a, b].
Будем
предполагать, что функция f(x) непрерывна на отрезке [a, b] (для метода хорд можно потребовать на
интервале) и имеет на этом интервале
первую и вторую производные, причём обе они знакопостоянны (в частности
отличны от нуля). Будем также предполагать, что функция f(x) принимает на концах отрезка значения разного знака. В силу
знакопостоянства первой производной функция f(x)
строго монотонна, поэтому при сделанных предположениях уравнение (1.1) имеет в точности один корень на
интервале (a, b).
2. Метод дихотомии
Этот
метод ещё называется методом вилки.
Нам
необходимо найти корень уравнения (1.1)
на отрезке [a, b]. Рассмотрим отрезок [x0, x1]: [x0, x1]Ì[a, b]. Пусть мы нашли такие точки х0,
х1, что f (х0)
f(х1) £
0, т. е. на отрезке [х0, х1] лежит не менее одного корня
уравнения. Найдём середину отрезка х2=(х0+х1)/2
и вычислим f(х2).
Из двух половин отрезка выберем ту, для которой выполняется условие
f (х2) f(хгран.) £
0, так как один из корней лежит на этой половине. Затем новый отрезок делим
пополам и выберем ту половину, на концах которой функция имеет разные знаки, и
т. д. (рис 1.2).
рис.
1.2
Если
требуется найти корень с точностью Е, то продолжаем деление пополам до тех пор,
пока длина отрезка не станет меньше 2Е. Тогда середина последнего отрезка даст значение корня с требуемой точностью. Дихотомия проста и очень надёжна. К простому корню она сходится для любых непрерывных функций
в том числе и не дифференцируемых; при
этом она устойчива к ошибкам округления. Скорость сходимости не велика; за одну
итерацию точность увеличивается примерно вдвое, т. е. уточнение трёх цифр
требует 10 итераций. Зато точность ответа гарантируется.
Приступим
к доказательству того, что если непрерывная функция принимает на концах
некоторого отрезка [a, b] значения разных знаков, то
методом дихотомии однозначно будет найден корень.
Предположим
для определённости, что функция f(x) принимает на левом конце
отрезка [a, b] отрицательное значение, а
на правом – положительное:
f(a) < 0, f(b) > 0.
Возьмём
среднюю точку отрезка [a,
b], h=(a+b)/2 и
вычислим значение в ней функции f(x). Если f(h)=0, то утверждение теоремы доказано: мы нашли такую точку, где
функция обращается в нуль. Если f(h)¹ 0, тогда из отрезков
[a, h] и [h, b]
выберем один из них тот, где функция на его концах принимает значения разных
знаков. Обозначим его [a1,
b1]. По
построению: f(a1)<0, f(b1)>0. Затем среднюю точку
отрезка [a1,
b1] точку h1 и проведём тот же алгоритм нахождения
другого отрезка [a2,
b2] где бы
по построению f(a2)<0, f(b2)>0. Будем продолжать
этот процесс. В результате он либо оборвётся на некотором шаге n в силу того, что f(hn)=0, либо будет
продолжаться неограниченно. В первом случае вопрос о существовании корня
уравнения f(x)=0 решён, поэтому
рассмотрим второй случай.
Неограниченное
продолжение процесса даёт последовательность отрезков [a, b], [a1,
b1], [a2, b2],… Эти отрезки
вложены друг в друга – каждый последующий отрезок принадлежит всем предыдущим:
an £ an+ 1 < bn+ 1 £ bn (1.2)
причём:
f(an) < 0, f(bn) > 0
Длины
отрезков с возрастанием номера n
стремятся к нулю:
Рассмотрим
левые концы отрезков. Согласно (1.2) они образуют монотонно убывающую
ограниченную последовательность {an}. Такая последовательность имеет
предел, который можно обозначить через c1: 
Согласно
(1.1) и теореме о переходе к пределу в неравенствах имеем:
c1
£
bn (2.2)
Теперь
рассмотрим правые концы отрезков. Они образуют монотонно не возрастающую ограниченную
последовательность {bn}, которая тоже имеет предел. Обозначим его
через с2: 
. Согласно неравенству (2.1) пределы с1 и с2
удовлетворяют неравенству с1 £ с2. Итак,
an £
с1 < с2 £ bn, и следовательно:
с2-с1
£
bn - an=(b-a)/2n.
Таким
образом, разность с2-с1 меньше любого наперёд заданного
положительного числа. Это означает, что с2-с1=0, т. е.: с1=с2=с
Найденная точка интересна тем, что она
является единственной общей точкой для всех отрезков построенной
последовательности Используя непрерывность функции f(x), докажем, что она
является корнем уравнения f(x)=0.
Мы
знаем, что f(an)<0. Согласно определению непрерывности и
возможности предельного перехода в неравенствах, имеем:
f(c)=lim
f(an)£0
(3.2)
Аналогично,
учитывая, что f(bn)³0, получаем, что:
f(c)=lim
f(bn) ³0
(4.2)
Из
(3.2) и (4.2) следует, что f(c)=0. т. е. с – корень уравнения.
Процесс
построения последовательности вложенных стягивающих отрезков методом вилки
(дихотомии) является эффективным вычислительным алгоритмом решения уравнения
f(x)=0. На n-ом шаге процесса получаем:
an
£
c £
bn
Это
двойное неравенство показывает, что число an определяет корень с
недостатком, а число bn с избытком, с ошибкой не превышающей длину
отрезка Dn=bn-an=(b-a)/2n.
При увеличении n ошибка стремится к нулю по закону геометрической прогрессии со
знаменателем q=0.5. Если задана требуемая точность e>0, то чтобы её
достигнуть достаточно сделать число шагов N, не превышающее log2[(b-a)/e]: N>log2[(b-a)/e].
3. Метод итераций
Этот
метод называется ещё методом последовательных приближений.
Пусть
нам необходимо найти корень уравнения (1.1) на некотором отрезке [a, b].
Предположим,
что уравнение (1.0) можно переписать в виде:
x=j(x) (1.3)
Возьмём
произвольное значение x0
из области определения функции j(x) и будет строить
последовательность чисел {xn},
определённых с помощью рекуррентной формулы:
xn +1=j(xn), n=0, 1, 2, … (2.3)
Последовательность
{xn}
называется итерационной последовательностью. При её изучении встают два
вопроса:
Можно ли процесс вычисления чисел xn продолжать неограниченно, т. е. будут ли числа xn принадлежать отрезку [a, b] ?
Если итерационный процесс (2.3)
бесконечен, то как ведут себя числа xn при n®¥
Исследование
этих вопросов показывает, что при определённых ограничениях на функцию j(x) итерационная последовательность
является бесконечной и сходится к корню уравнения (1.3).
, c=j(c) (3.3)
Однако
для того, чтобы провести это исследование нам нужно ввести новое понятие.
Говорят,
что функция f(x) удовлетворяет на отрезке [a, b] условию Липшица, если существует
такая постоянная a,
что для любых x1,
x2, принадлежащих
отрезку [a, b] имеет место неравенство:
|
f(x1) - f(x2)| £ a|x1 - x2| (4.3)
Величину
a
в этом случае называют постоянной Липшица.
Если
функция f(x), удовлетворяет на отрезке
[a, b] условию Липшица, то она непрерывна на
нём. Действительно, пусть x0
– произвольная точка отрезка. Рассмотрим приращение функции f(x) в этой точке:
Df=f(x0+Dx) – f(x0)
и
оценим его с помощью неравенства (4.3)
|Df | £ a|Dx|
Таким
образом, 
, что означает непрерывность функции f(x).
Условие
Липшица имеет простой геометрический смысл. Возьмём не графике функции y=f(x) две произвольные точки M1 и M2 с координатами
(x1, f(x1)) и (x2, f(x2)). Напишем уравнение прямой линии, проходящей через
эти точки:
y=f(x1) + k(x-x1)
где
k– тангенс угла наклона
прямой у оси Оx и
определяется формулой:
Если
функция f(x) удовлетворяет на отрезке [a, b] условию Липшица, то при произвольном
выборе точек M1
и M2 имеем |k|£a.
Таким образом, с геометрической точки зрения условие Липшица означает
ограниченность тангенса угла наклона секущих, проведённых через всевозможные
пары точек графика функции y=f(x).
рис
2.3 геометрическая иллюстрация условия Липшица.
рис
3.3 геометрическая иллюстрация cвязи условия Липшица с предположением о
дифференцируемости функции.
Предположим,
что функция f(x) имеет на отрезке [a, b] ограниченную производную:
|
f ¢(x)| £ m;
тогда она удовлетворяет условию Липшица с постоянной a=m. Для доказательс- тва этого
утверждения воспользуемся формулой конечных приращений Лагранжа:
f(x2) – f(x1) = f ¢(x)(x2-x1) (5.3)
где
x1, x2,
- произвольные точки отрезка [a,
b] x,
- некоторая точка отрезка [x1,
x2]. Возьмём
модуль обеих частей равенства (4.3) и заменим в правой части | f ‘(x)| на m. В результате по- лучим неравенство
(4.3) с a=m. Рис.2.3 даёт
геометрическую иллюстрацию установленного свойства. Согласно формуле Лагранжа
(5.3) каждой секущей графика функции y = f(x) мож- но поставить в
соответствие параллельную её касательную. Поэтому наибольший тангенс угла
наклона касательных, и его можно оценить той же константой m: |k| £
m.
Познакомившись
с условием Липшица, перейдём к изучению итерационной последовательности,
предполагая, что уравнение имеет корень x=c.
Существование этого корня можно установить с помощью качественного
предварительного исследования уравнения с применением теоремы о существовании
корня непрерывной функции.
Теорема о существовании корня непрерывной функции
Если
функция f(x) непрерывна на отрезке [a, b] и принимает на его концах значения
разных знаков, то на этом отрезке существует, по крайней мере, один корень
уравнения f(x).
Теорема
о сходимости итерационной последовательности
Пусть
с – корень уравнения (2.3) и пусть функция j(x) удовлетворяет на некотором отрезке [c-d, c+d] (d>0) условию Липшица с
постоянной a<1.
Тогда при любом выборе x0
на отрезке [c-d, c+d] существует бесконечная
итерационная последовательность {xn} и эта последовательность сходится к корню x=c, который является единственным
решением уравнения (1.3) на отрезке [c-d,
c+d].
Сформулированная
теорема имеет очень простой смысл. Будем говорить, что функция j
осуществляет отображение точки x
на точку y=j(x). Тогда условие Липшица с
постоянной a<1
означает, что отображение j является сжимающим: расстояние между точками x1 и x2 больше, чем
расстояние между их изображениями y1=j(x1)
и y2=j(x2).
Корень
c является неподвижной
точкой отображения j,
он преобразуется сам в себя c=j(c). Поэтому каждый шаг в
итерационном процессе, сжимая расстояния должен приближать члены
последовательности {xn}
к неподвижной точке c.
После
таких соображений поясняющих смысл теоремы, перейдём к её доказательству.
Возьмём произвольную точку x0
на отрезке [c-d, c+d], она отстоит от точки c не больше чем на d: |c-x0| £ d.
Вычислим
x1: x1=j(x0), при этом x1-c =j(x0)-j(c). Разность j(x0)-j(c) можно оценить с помощью условия
Липшица:
|x1-c| = |j(x0)-j(c)| £
|x0-c| £ ad. (6.3)
Неравенство
(6.3) показывает, что x1
принадлежит отрезку [c-d, c+d] и расположен ближе к
точке c, чем x0.
Продолжим
построение итерационной последовательности. Вычислим x2: x2=j(x1), при этом:
|x2-c| = |j(x1)-j(c)| £ a|x1-c| £ a2|x0-c| £ a2d
Точка
x2 опять
принадлежит отрезку [c-d, c+d] и расположена ближе к
точке c, чем точка x1, т.е. мы
приблизились к c.
По
индукции легко доказать, что последующие итерации также существуют и
удовлетворяют неравенствам.
|xn-c| £ an |x0-c| £ and (7.3)
Отсюда
следует, что:
, т. е. 
Остаётся
доказать, что корень x=c (1.3) является единственным
решением уравнения на отрезке [c-d, c+d].
Действительно, допустим, что существует ещё один корень x=c1.
Примем
c1 за
нулевое приближение и будем строить итерационную последователь- ность (2.3).
Тогда с учётом (7.3) получим xn=c1 (n=0, 1, 2, …). С другой
стороны, по доказанному , т. е. c1=c. Никаких других решений
уравнение на отрезке иметь не может.
Сходимость
итерационной последовательности к корню уравнения (1.3) может быть использована
для приближённого определения корня с любой степенью точности. Для этого нужно
только провести достаточное количество итераций.
4. Быстрота сходимости процесса итераций
Используем
теперь производную функции j(x)
для оценки скорости сходимости итераций при решении уравнения х=j(x). Нужно оценить скорость, с
которой убывают погрешности an=x-xn приближённых значений х1, … , хn, … корня x.
рис
1.4
Можно
заметить, что справедливы равенства x=j(x) и хn+ 1=j(хn).
Из них вытекает, что:
an+ 1= x-хn+ 1=j(x)-j(хn)
Но
по формуле Лагранжа имеем:
j(x)-j(хn)= j ¢(cn)·( x-xn)= j ¢(cn) ·an
где
cn - точка
лежащая между точками x и хn.
Поэтому:
an+ 1=j ¢(cn) ·an (1.4)
Из
равенства (1.4) вытекает следующий вывод:
Пусть
x
– корень уравнения x=j (x) - лежит на отрезке [a, b]. Если на этом отрезке выполняется
неравенство |j
¢(x)|<q<1, а начальное приближение x1
также выбрано на отрезке [a,
b], то при любом n выполняется соотношение:
|an+ 1|<qn·|a1|
(2.4)
В
самом деле, из равенства (1.4) имеем:
|a2|=|j ¢(c1)|·|a1|
Но
точка c1
лежит на отрезке [a, b] (рис.1.4), и потому:
|j ¢(c1)|<q
Отсюда
следует, что:
|a2|<q·|a1|
Точно
так же получаем, что:
|a3|=|j ¢(c1)|·|a2|<q·|a2|< q2·|a1|
и
вообще:
|an+
1|=qn·|a1|
Тем
самым наше утверждение доказано.
Так
само при 0<q<1 последовательность
чисел q, q2,
q3, … , qn,
… стремится к нулю, то и погрешность an+ 1 стремится к нулю с
возрастанием n. Иными словами, при указанных выше предположениях числа x1, x2, … , xn, … приближаются
к числу x,
причём разность |x-xn| убывает
быстрее, чем qn·|a1|.
Точно
так же можно