Решение нелинейных уравнений

Решение уравнения с одним неизвестным
Дано уравнение в виде f(x)=0, где f(x) некоторая функция переменной x. Число x* называется корнем или решением данного уравнения, если при подстановке x= x* в уравнение последнее обращается в тождество. f(x*)=0. Число x* называют также нулем функции y=f(x).
В общем случае уравнение может иметь одно или несколько корней, как действительных, так и комплексных. Нахождение действительных корней с заданной точностью можно разбить на два этапа: отделение корней, т.е. определяются отрезки, которые содержат только один корень уравнения; а затем уточнение, т.е. вычисляются корни с требуемой точностью ε.
Отделение корней уравнения f(x)=0, в области определения, непрерывной функции f(x), можно осуществлять несколькими способами: табулированием и графически
Табулирование – составление таблицы из равноотстоящих значений независимой переменной x и соответствующих значений функции и определение отрезков в которых смежные значения функции имеют различные знаки и следовательно содержат нулевые значения функции.
Графический - строим график функции f(x) и определяем минимальные отрезки, включающие точки пересечения графика функции с осью x.

пример: f(x) = 3*sin(2*x)-1,5*x-1=0

Построение графика функции
f=inline(‘3*sin(2*x)-1.5*x-1‘)
a=input (‘a=‘);
b=input (‘b=‘);
h=input (‘h=‘);
x=a :h :b;
plot (x, f (x)); grid
xlabel (‘x’); ylabel (‘f (x)’)

Уточнение корня на отрезке [a,b], в котором локализован только один корень, осуществляется итерационными методами, в которых последовательно, шаг за шагом, производится уточнение начального приближения корня. Итерацией называется совокупность вычислительных операций, приводящих к новому приближенному значению корня. Если каждое последующее значение x(k) (k=1,2,3,…) находится все ближе к точному значению, говорят, что метод сходится. В противном случае метод расходится. Для реализации итерационного процесса должны быть заданы начальное приближение x(0) и точность ε, с которой найти решение уравнения. Условие окончание имеет вид: |x(k)-x(k-1)| ≤ ε
Метод половинного деления ( М П Д )
В этом методе на каждой итерации новое приближение определяется как:
x(k)=( a(k-1)+b(k-1) )/2, где к – н о м е р и те р а ц и и.
Алгоритм
Заданы функция f(x), отрезок [a(0),b(0)], точность ε. Пусть k=1.
В ы ч и с л я е м приближение x(k)=(a(k-1)+b(k-1)) / 2
О п р е д е л я е м новый отрезок [a(k),b(k)]. Проверяем, если f(a(k-1))*f(x(k))>0, то a(k)=x(k) и b(k)=b(k-1) (остается прежним), иначе b(k)=x(k) и a(k) -остается прежним.
П р о в е р я е м условие окончания, если |b(k)-a(k)| ≤·2ε, то за ответ принимаем значение равное x=(a(k)+b(k))/2 и переходим на пункт 5, иначе k=k+1 и переходим на пункт 2.
В ы в о д x и f(x).

Блок-схема
начало
f (a)*f (x)>0
x, f(x)
a, b, ε || f(x)
b = x
a = x
x = (b+a) / 2
| b - a | > 2ε
конец
x = (b+a)/2
нет
да
да

Достоинства и недостатки метода
Достоинства
1.Метод сходится всегда (абсолютная сходимость)
2.Можно заранее определить количество итераций для получения решения
n = ln ((b-a) /(eps))-1
Недостатки
1. При требовании высокой точности решения необходимо большое количество итераций, т.е. метод медленный и рекомендуется использовать только для ориентировочного нахождения решения

Решим предыдущий пример при a= -1,6 b= -1,2 и ε= 0,01 т.е. 2ε = 0,02
x= –1,38±0,01 f (x) = –0,038 (невязка)

Метод простых итераций (МПИ)
Преобразуем исходное уравнение f(x)=0 к эквивалентному виду x=ϕ(x). Тогда на каждой итерации новое приближение будем определять как:
x(1) = ϕ (x(0)), x(2) = ϕ (x(1)), x(3) = ϕ (x(2)),….., т.е. x(k)=ϕ(x(k-1)), k=1,2,3… . .
Для оценки сходимости метода проверяем достаточное условие сходимости, которое записывается как:
|ϕ ’(x)| < 1, для всех значений x отрезка[a;b], т.е. максимальная производная на заданном отрезке должна быть меньше единицы.
Общий подход для получения итерационной формулы x=ϕ(x)
Умножим обе части уравнения f(x)=0 на множитель β , который будет обеспечивать выполнение достаточного условия сходимости β f(x)=0
и прибавим к обеим частям по x, тогда итерационная формула будет иметь вид:
x = x + βf (x) = ϕ(x)
Определить множитель β можно из достаточного условия сходимости.
|ϕ’(x)| < 1
ϕ’(x) = 1 + β*f ’(x)
|1 + β*f ’(x)| < 1
-1 < 1 + β*f ’(x) < 1
-2 < β*f ’(x) < 0.
Мы должны выбрать максимальную по модулю производную |f’(x)| на заданном отрезке.
|f ’(b)|>|f ’(a)| β = -2/f ’(b),иначе β = -2/ f ’(a)

Блок-схема
да
да

Пример: f (x) = 3sin(2x)-1,5x-1 f '(x)=6cos(2x)-1,5 ε=0,01 a = -1,6 b = -1,2
f '(a) = -7,489 f '(b) = -5,924 β = 0,267 ≈ 0,2
x (k) = x(k-1) + β* (3sin(2x(k-1))-1,5x(k-1)-1)
Ответ: x = -1,38±0,01 f(x) = -0,020

Метод Ньютона (метод касательных)
Пусть известно некоторое приближение x(k-1) к решению x* уравнения f(x)=0.
Необходимо найти такое ∆x(k) , чтобы :
f(x(k-1)+∆x(k))=0
где ∆x(k)= x* -x(k-1) и x* = x(k-1)+ ∆x(k)
Разложим функцию в ряд Тейлора и ограничимся линейными членами.
f(x(k-1)+∆x(k)) = f(x(k-1))+ f ′(x(k-1))∆x(k) = 0
откуда
Полученное значение принимаем за новое приближение к решению. Тогда итерационную формулу запишем как:

Графическая иллюстрация.
За начальное приближение к корню x(0) принимаем одну из границ отрезка [a; b], содержащего один корень.
На каждой итерации, за новое приближение к корню x(k) принимается точка пересечения касательной к графику, построенной в точке f(x(k-1)) с осью абсцисс x:

Алгоритм метода Ньютона
Заданы функция f(x) отрезок [a;b] и точность ε. За начальное приближение x принимаем одну из границ заданного отрезка [a,b]. Например x=a.
Вычисляем значение шага h= f(x)/f ′(x) и новое приближение, как x = x-h.
Проверяем условие окончания если | h | ≤ ε, то выводим последнее значение x и f(x). Иначе перейдем на пункт 2
Блок-схема

a = -1,6 b = -1,2 ε = 0,01 f (x)=3sin(2x) -1,5x-1 f '(x)=6cos(2x) -1,5 x=a= -1.6
Ответ: x = 1,387± 0,01 f (x)=0,00002
Пример

Достоинства и недостатки
метода
Достоинства:
Быстрая сходимость
Недостатки:
Необходимость вычисления производных
При неправильном выборе начального приближения возможен выход решения за границы интервала ( расходимость метода). Метод будет сходиться, если в начальной точке выполняется соотношение
f ( x) * f ’’(x) > 0