Методы решения нелинейных уравнений - Мои статьи - Каталог статей - TRIM.MY1.RU
Главная » Статьи » Мои статьи

Методы решения нелинейных уравнений

Методы решения нелинейных уравнений

При решении практических задач часто приходится сталкиваться с решением уравнений. Всякое уравнение с одним неизвестным можно представить в виде φ (x)=q(x). φ(x) и q(x) определены на некотором числовом множестве х называемом областью допустимых значений уравнения. Если в уравнении φ(x)=q(x) правую часть перенести в лево, то получим разность φ(x)-q(x)=0 Обозначим разность φ(x)=q(x) как f(x)=0. Это общая форма записи уравнения с одним неизвестным.

Совокупность значений переменных х, при котором уравнение f(x)=0 превращается в тождество, называется решением данного уравнения, а значение х – корнем данного уравнения.

Решить уравнение значит найти множество всех корней этого уравнения, которое может быть конечным и бесконечным.

В зависимости от того, какие функции входят в уравнение φ(x)=q(x) или f(x)=0 все уравнения разделяются на алгебраические и трансцендентные. Алгебраические и трансцендентные уравнения называются нелинейными.

Функция называется алгебраической, если для получения значения функции по данному значению аргумента нужно выполнить арифметические операции и возведение в степень с рациональным показателем. Если в записи уравнения входят только алгебраические функции, то такое уравнение называется алгебраическим.

Вторую группу составляют трансцендентные уравнения в которые входят трансцендентные функции (ax, ex, logax, ln x, lg x).

Найти точное значение корней нелинейных уравнений можно только в исключительных случаях.

Задача нахождения корней уравнения считается решенной, если корни вычислены с заданной

Процесс нахождения приближенных значений корней уравнения разбивается на два этапа:

отделение корней;

уточнение корней.


Отделение корней

Пусть ξ – точный корень уравнения f(x)=0. Корень ξ считается отделенным на отрезке [a,b], если уравнение на этом отрезке не имеет других корней.

Отделить корни значит разбить область допустимых значений на отрезки, в каждом из которых находится один корень.

Отделение корней можно производить двумя путями:

графически;

аналитически.

Уточнение корней

Вторым этапом решения нелинейных уравнений является уточнение корней, т.е. доведение их до заданной степени точности.

Существует несколько методов для решения алгебраических и трансцендентных уравнений.


Метод проб

Вторым этапом решения нелинейных уравнений является уточнение корней, т.е. доведение их до заданной степени точности. Метод проб применяется для решения алгебраических или трансцендентных уравнений. Для составления программ и расчетов не ЭВМ метод проб применятся в виде так называемого метода половинного деления. Суть этого метода заключается в следующем.

Дано уравнение f(x)=0. Корень x  отделен и принадлежит отрезку [a,b], это значит: f(a)f(b)<0

Возьмем на отрезке [a,b] промежуточную точку с=(a+b)/2, тогда отрезок [a,b] разделится на два равных отрезка [a,c] и [c,b] (см. рисунок)


Если f(c)=0, то точка с является корнем уравнения.

Если f(c)¹ 0 то из двух отрезков [a,c] и [c,b] выберем тот, на концах которого функция принимает значения разных знаков. Пусть это отрезок [c,b]. Обозначим его через [a1,b1]. Затем этот отрезок делим на два. Получаем с1=(a1+b1)/2. Проверяем, f(c1)=0. Если нет, то из двух отрезков [a1c1] и [c1b1] выбираем тот на концах которого функция y=f(x) имеет разные знаки. Пусть это будет отрезок [a1c1]. Обозначим его [a2b2]. Отрезок делим на два и получаем c2 и так далее.

Процесс деления отрезка проводим до тех пор, пока на каком то n-ом этапе получим отрезок [anbn] такой, что |an-bn|£e . Здесь e заданная точность вычисления. Числа an и bn являются корнями уравнения с точностью до e

За приближенное значение корня следует взять x =(an+bn)/2


Метод хорд для уточнения корней

Данный метод является одним из наиболее распространенных методов решения нелинейных уравнений. Его называют методом линейного интерполирования или методом пропорциональных частей.

Пусть задана некоторая функция f(x)=0. Функция f(x) непрерывна на отрезке [a,b] и имеет производные первого и второго порядка.

Корень считается отделенным и находится на отрезке [a,b] т.е. f(a)f(b)<0.

Идея метода хорд состоит в том, что на достаточно малом промежутке [a,b] дуга кривой функции y=f(x) заменяется стягивающей ее хордой. В качестве приближенного значения корня принимается точка пересечения с осью OX

I.Рассмотрим случай, когда f'(x)f"(x)>0.

Для этого случая характерны графики функций представленные на рис.1 и рис.2.

График функции проходит через точки А0(a,f(a)) и B(b,f(b))

  

Искомый корень уравнения f(x)=0 это абсцисса точки пересечения графика функции y=f(x) c осью OX (точка x). Эта точка не известна. Вместо нее будем рассматривать точку x1, которая является точкой пересечения хорды A0B с осью OX. Это будет первое приближение корня x. Значение координаты x1 вычисляется по формуле (1). В общем случае нахождение n+1 приближения осуществляется по формуле (2). Следует заметить, что все приближенные значения корня вычисляются с недостатком.

(1)

; x0=a (2)

II. Рассмотрим случай, когда f'(x)f"(x)<0

Для этого случая характерны графики функций, представленные на Рис.3 и Рис.4.

Рис 3.

Рис 4.

Для данного случая ситуация аналогична. Корень x уравнения неизвестен. Для его нахождения будет рассматривать приближенные значения корня, которые являются точками пересечения хорд АnB с осью ОХ. Для вычисления первого приближения можно воспользоваться формулой (3), а для вычисления всех последующих формулой (4). Для данного случая все приближенные значения корня уравнения вычисляются с избытком.

(3)

; x0=b (4)

Итак, если f'(x)f"(x)>0, то приближенный корень вычисляется по формулам 1 и 2. Если f'(x)f"(x)<0, то приближенный корень уравнения вычисляется по формулам 3 и 4.

Однако выбор тех или иных формул можно осуществить пользуясь простым правилом. Неподвижным концом отрезка является тот, для которого знак функции совпадает со знаком второй производной от этой функции.

Процесс вычисления продолжается до тех пор, пока модуль разности между двумя соседними приближениями не станет меньше допустимой погрешности вычисления ε, т.е. |xn+1-xn|< ε, и тогда в качестве приближенного значения корня принимается xn+1 приближение.





Метод Ньютона (метод касательных) для уточнения корней нелинейных уравнений

Геометрический смысл метода Ньютона состоит в том, что дуга кривой y=f(x) заменяется касательной к этой прямой, откуда следует второе название этого метода - метод касательных

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

I. f'(x)f"(x)>0

Для этого случая характерны графики, представленные не рис.1 и рис.2

Если провести касательную к кривой y=f(x) в точке А, то она пересечет координатную ось ОХ в точке не принадлежащей интервалу [a,b]. Это означает, что точка А будет неподвижной, а начальное приближение корня x будет определяться точкой пересечения касательной, проведенной из точки B с координатной осью OY.

Рис.1

Рис.2

Проведем касательную к кривой y=f(x) в точке B0(b;f(b)) и найдем абсциссу точки пересечения касательной с координатной осью ОХ (точка x1). Это значение можно вычислить использую формулу (1), которая вытекает из уравнения касательной к графику функции y=f(x) в точке B0. Найденное значение будет первым приближением корня x. В общем случае формулу (1) можно записать в виде формулы (2), которая подходит для вычисления всех последующих приближений корня x.

(1)

x0=b (2)

Таким образом получаем последовательность приближенных значений, каждый член которой ближе к корню x чем предыдущий, однако все xn>x, следовательно xn+1 приближенное значение корня x с избытком.

II. f'(x)f"(x)<0

Для этого случая характерны графики функций, представленные на рис.3 и рис.4

Если провести касательную к кривой f(x)=0 в точке B, то она пересекет координатную ось ОХ в точке не принадлежащей отрезку [a,b]

Рис.3

Рис.4

Проведем касательную к кривой y=f(x) в точке А0(a;f(a)) и найдем абсциссу точки пересечения касательной с координатной осью OX. Это значаение вычисляется по формуле (3), которая следует из уравнения касательной к графику функции y=f(x) в точке A0 и является первым приближением корня x. В общем случае для вычисления остальных приближений можно воспользоваться формулой (4), которая является общей формулой для нахождения n+1 приближения корня x.

(3)

x0=a (4)

При выборе начального приближения корня можно руководствоваться правилом

За исходную точку x0 следует выбирать тот конец отрезка [a,b] на котором знак функции совпадает со знаком второй производной от этой функции.

Процесс вычисления продолжается до тех пор, пока модуль разности между двумя соседними приближениями не станет меньше заданной погрешности вычисления e, т.е. |xn+1-xn|<e. За приближенное значение корня x при этом следует взять xn+1 приближение.



Комбинированный метод хорд и касательных для уточнения корней нелинейных уравнений

Методы хорд и касательных дают приближения корня с разных сторон. Поэтому их часто принимают в сочетании друг с дригом.

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

Если f'(x)f"(x)>0, то метод хорд дает приближения корня с недостатком, а метод касательных с избытком. Если же f'(x)f"(x)<0, то методом хорд получаем значения корня с избытком, а методом касательных - с недостатком. Однако во всех случаях значение корня x заключено между прибближенными значениями корней, полученными методом хорд и методом касательных, т.е. выполняется равенство a<xнn<x<xиn <b, где xнn-приближение по недостатку, а xиn-приближение по избытку.

I. Если f'(x)f"(x)>0

Для этого случая характерны графики, представленные не рис.1 и рис.2

Рис.1

Рис.2

В качестве начального приближения для метода хорд следует взять конец а, для метода касательных конец b, и тогда воспользуясь формулами (1) и (2) получим первое приближение корня x. Теперь истинный корень находится на отрезке [a1,b1]. Применим к этому отрезку комбинированный метод и получим второе приближение корня и так далее находим все последующие приближения корня x используя формулы (3) и (4).

(1)

(2)

(3)

(4)

II. Если f'(x)f"(x)<0

Для этого случая характерны графики функций, представленные на рис.3 и рис.4

Рис.3

Рис.4

Если провести касательную к кривой f(x)=0 в точке B, то она пересекет координатную ось ОХ в точке не принадлежащей отрезку [a,b]

Тогда в качестве начального приближения для метода хорд следует взять конец b, для метода касательных - конец a. Тогда первое приближение корня x вычилсяется по формулам (5) и (6). Все последующие приближения используют формулы (7) и (8).

(5)

(6)


(7)

(8)

Комбинированный метод очень удобен при оценке погрешности вычислений. Процесс вычислений прекращается, как только будет выполнено неравенство |an-bn|<e

За приближенное значение корня x при этом следует взять x=(an+bn)/2.


Метод итераций (последовательных приближений) для уточнения корней нелинейных уравнений

Одним из наиболее распространенных методов решения нелинейных уравнений является метод итераций.

Основное его приемущество - однотипность, выполняемых на каждом шаге операций, что в значительной степени облегчает составление программ для ЭВМ

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

Заменим уравнение (1) эквивалентным уравнением (2).x=u(x)
В этом уравнении искуственно любым способом оставляют слева x, перенося все остальное вправо

Уравнение (2) называют уравнением приведенным к виду, удобному для итерации. Уравнение (2) имеет те же корни, что и уравнение (1).

Представление функции в виде u(x) может быть установленно бесчисленным множеством способов. Кроме того вид u(x) оказывает существенное влияние как на сам факт сходимости, так и на ее скорость. Выберем каким либо образом грубо начальное приближение x0 (можно графически или используя формулу x0=(a+b)/2) и подставим его в правую часть уравнения (2). Тогда получим некоторое число x1, которое равно u(x0). Далее полученное значение x1 вновь подставляем в правую часть уравнения (2) и получим некоторое значение x2 и т.д. Каждое новое приближение корня уравнения вычисляется по формуле xn+1=u(xn), n>0. Получим последовательность приближений x0, x1, ... ,xn

Возможны два случая:

1.       последовательность сходится, т.е. имеет предел и тогда этот предел является корнем уравнения (2), а следовательно и уравнения (1);

2.       последовательности расходится, т.е. не имеет предела.

Геометрически способ итерации может быть пояснен так. На плоскости OXY построим графики y=x и y=u(x), т.е. обе части уравнения (2). Каждый действительный корень уравнения (2) является абсциссой пересечения этих линий (см. рис.1).

Рис.1
Здесь x0 - начальное приближение, которое мы выбираем сами.

Отправляясь от некоторой точки A0(x0;u(x0)) строим ломаную линию (лестницу), звенья которой попеременно параллельны оси OX и OY, вершины A0, A1 и т.д. лежат на кривой y=u(x), а вершины B1, B2 и т.д. лежат на прямой y=x, общие абсциссы этих точек (представяют последовательные приближения x1, x2 и т.д.) корня x

Решение в виде "лестиницы" получается если u'(x)>0, на рис.1 кривая y=u(x) в окрестности корня x пологая, т.е. |u'(x)|<1 и процесс итерации сходится. Однако, если рассмотреть случай, где |u'(x)|>1, то процесс итерации может быть расходящимя по лестнице.

Если u'(x)<0, то решение получается в виде спирали. (см. рис.2 и рис. 3).

Рис.2

Рис.3

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

Достаточное условие сходимости процесса итерации

Пусть функция u(x) определена и дифференцируема на интервале [a,b], тогда, если существует число q, такое, что выполняется условие |u'(x)|<=q<1,
то процесс итерации xn+1=u(xn) сходится независимо от начального приближения x0 не выходящего за границы интервала [a,b]. Корень x уравнения определяется как x=lim xn+1

q=max(u'(x)). Чем меньше |u'(x)|, тем лучше сходимость итерационного процесса.

Замечание

Так как итерационный процесс сходится независимо от начального приближения x0, принадлежащего интервалу [a,b], то он является самоисправляющимся, поэтому отдельная ошибка в вычислениях, не выходящая за рамки интервала [a,b] не влияет на конечный результат. В этом случае ошибочное значение может рассматриваться как новое приближение, возрастает лишь объем работы.

Точность вычислений.

Последовательность приближений x0, x1 ..., xn вычисляется до тех пор, пока не будет выполнено неравенство
|xn+1-xn|<=e(1-q)/q



Категория: Мои статьи | Добавил: trim (21.12.2009)
Просмотров: 5862 | Комментарии: 2 | Рейтинг: 4.7/3
Всего комментариев: 2
Имя *:
Email:
Код *: