Приближённые методы решения алгебраического уравнения
Реферат по курсу
численных методов выполнил студент группы РЭ–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.
Возьмём
среднюю точку отрезка [a,
b], h=(a+b)/2 и
вычислим значение в ней функции f(x). Если f(h)=0, то утверждение теоремы доказано: мы нашли такую точку, где
функция обращается в нуль. Если f(h)¹ 0, тогда из отрезков
[a, h] и [h, b]
выберем один из них тот, где функция на его концах принимает значения разных
знаков. Обозначим его [a1,
b1]. По
построению: f(a1)0. Затем среднюю точку
отрезка [a1,
b1] точку h1 и проведём тот же алгоритм нахождения
другого отрезка [a2,
b2] где бы
по построению f(a2)0. Будем продолжать
этот процесс. В результате он либо оборвётся на некотором шаге n в силу того, что f(hn)=0, либо будет
продолжаться неограниченно. В первом случае вопрос о существовании корня
уравнения f(x)=0 решён, поэтому
рассмотрим второй случай.
Неограниченное
продолжение процесса даёт последовательность отрезков [a, b], [a1,
b1], [a2, b2],… Эти отрезки
вложены друг в друга – каждый последующий отрезок принадлежит всем предыдущим:
an £ an+ 1
причём:
f(an) 0
Длины
отрезков с возрастанием номера n
стремятся к нулю:
Рассмотрим
левые концы отрезков. Согласно (1.2) они образуют монотонно убывающую
ограниченную последовательность {an}. Такая последовательность имеет
предел, который можно обозначить через c1:
Согласно
(1.1) и теореме о переходе к пределу в неравенствах имеем:
c1
£
bn (2.2)
Теперь
рассмотрим правые концы отрезков. Они образуют монотонно не возрастающую ограниченную
последовательность {bn}, которая тоже имеет предел. Обозначим его
через с2: . Согласно неравенству (2.1) пределы с1 и с2
удовлетворяют неравенству с1 £ с2. Итак,
an £
с1
с2-с1
£
bn - an=(b-a)/2n.
Таким
образом, разность с2-с1 меньше любого наперёд заданного
положительного числа. Это означает, что с2-с1=0, т. е.: с1=с2=с
Найденная точка интересна тем, что она
является единственной общей точкой для всех отрезков построенной
последовательности Используя непрерывность функции f(x), докажем, что она
является корнем уравнения f(x)=0.
Мы
знаем, что f(an)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