Приближённые методы решения алгебраического уравнения
Другие рефераты
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) называется такое число (, где f(()=0.
При определении приближённых корней уравнения (1.1) необходимо
решить две задачи:
1) отделение корней, т. е. определение достаточно малых промежутков, в
каждом из которых заключён один и только один корень уравнения
(простой и кратный);
2) уточнение корней с заданной точностью (верным числом знаков до или
после запятой);
Первую задачу можно решить, разбив данный промежуток на
достаточно большое количество промежутков, где бы уравнение имело ровно
один корень: на концах промежутков имело значения разных знаков. Там где
данное условие не выполняется, те промежутки откинуть.
Вторая задача решается непосредственно в методах рассмотренных
ниже.
При графическом отделении корней уравнения (1.1) нужно последнее
преобразовать к виду:
(1(x)=(2(x)
(2.1)
и построить графики функций y1=(1(x), y2=(2(x).
Действительно, корнями уравнения (1.1)
f(x) = (1(x) - (2(x) = 0
являются абсциссы точек пересечения этих графиков (и только они).
Из всех способов, какими можно уравнение (1.1) преобразовать к
виду (2.1) выбираем тот, который обеспечивает наиболее простое построение
графиков y1=(1(x) и y2=(2(x). В частности можно взять (2(x) = 0 и тогда
придём к построению графика функции (1.1), точки пересечения которого с
прямой y2=(2(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).
Если требуется найти корень с точностью Е, то про-
должаем деление пополам до тех пор, пока длина отрезка
не станет меньше 2Е. Тогда середина последнего отрезка
даст значение корня с требуемой точностью.
Дихотомия проста и очень надёжна. К простому
корню она сходится для любых непрерывных функций
в том числе и не дифференцируемых; при этом она устой-
чива к ошибкам округления. Скорость сходимости не ве-
лика; за одну итерацию точность увеличивается пример-
но вдвое, т. е. уточнение трёх цифр требует 10 итераций.
Зато точность ответа гарантируется.
рис. 1.2
Приступим к доказательству того, что если непрерывная функция
принимает на концах некоторого отрезка [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
| |  скачать работу |
Другие рефераты
|
