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

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

Алгебраическое уравнение - ной степени задается в следующем виде:

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

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

· этап отделения корней

· этап уточнения корней

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

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

· Табличный способ. Строится таблица, состоящая из двух строк, в первой строке с каким-то произвольным шагом изменяется значение аргумента , желательно на отрезке симметричном относительно . Во второй строке вычисляются соответствующие значения функции . Если в соседних ячейках второй строки функция меняет знак (причем неважно с + на – или с - на +), то считается что на этом интервале находится хотя бы один корень.

· Способ нахождения верхних и нижних границ положительных и отрицательных корней.

Метод деления отрезка пополам

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

 

 

Рис. 4

Очевидно, что середина отрезка на рис. 4 служит приближением к искомому корню уравнения. Обозначим середину отрезка точкой . В этой точке определяется знак функции , затем выбирается та половина отрезка, на концах которой функция принимает значения разных знаков и деление повторяется по тому же самому алгоритму. Если требуется найти корень с точностью , то деление отрезка пополам продолжается до тех пор, пока длина последнего отрезка содержащего корень не станет меньше величины . Тогда середина последнего отрезка даст значение корня с требуемой точностью. В этом методе можно не вычислять само значение функции , достаточно лишь определить знак значения функции. Обозначим погрешность на шаге через , где - точное значение корня, тогда погрешности на - том и шаге связаны неравенством , где , что позволяет отнести метод деления отрезка пополам к методам, имеющим линейную скорость сходимости.

Пример: уточнить корень уравнения , находящийся на методом деления отрезка пополам с точностью .

1. Находим . Вычисляем значения функции в точке

Отсюда следует, что корень находится на отрезке .

Длина этого отрезка процесс по методу деления отрезка пополам следует продолжить.

2. Находим . Вычисляем значения функции в точке

Отсюда следует, что корень находится на отрезке .

Длина этого отрезка процесс по методу деления отрезка пополам следует продолжить.

3. Находим . Вычисляем значения функции в точке

Отсюда следует, что корень находится на отрезке .

Длина этого отрезка процесс по методу деления отрезка пополам следует продолжить.

4. Находим . Вычисляем значения функции в точке

Отсюда следует, что корень находится на отрезке .

Длина этого отрезка процесс по методу деления отрезка пополам следует продолжить.

5. Находим . Вычисляем значения функции в точке

Отсюда следует, что корень находится на отрезке .

Длина этого отрезка процесс по методу деления отрезка пополам следует продолжить.

6. Находим . Вычисляем значения функции в точке

Отсюда следует, что корень находится на отрезке .

Длина этого отрезка процесс по методу деления отрезка пополам следует закончить.

Середина отрезка дает корень с заданной степенью точности .

Метод Ньютона

Метод Ньютона применяется к решению уравнения, когда функция является непрерывно дифференцируемой функцией. Также вначале отделим корень уравнения на отрезке .

Рис. 5

Для начала вычислений требуется задание одного начального приближения внутри отрезка . Первое приближение вычисляется через это начальное по формуле рис. 5:

Общая формула метода Ньютона может быть записана с помощью рекуррентного соотношения:

,

где и .

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

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

а сомножители выбираются так, чтобы выполнялось неравенство

.

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

Условием выхода из итерационного процесса по методу Ньютона является выполнение неравенства

Пример: уточнить корень уравнения , находящийся на методом Ньютона с точностью .

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

1. По рекуррентной формуле метода Ньютона вычислим

вычисления по методу Ньютона следует продолжить.

2. По рекуррентной формуле метода Ньютона вычислим

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

Метод простой итерации

Метод простой итерации применяется к решению уравнения с выделенным значением неизвестного в правой части и состоит в построении последовательности , начиная с некоторого начального значения по правилу

Если непрерывная функция, а - сходящаяся последовательность, то значение является корнем уравнения.

Условием сходимости процесса итераций, т.е. условие существования предела есть соблюдение неравенства, носящего название принципа сжатых отображений:

,

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

,

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

.

При этом предполагается, что чем больше проделано уточнений, тем выше точность определения корня.

Метод простой итерации имеет линейную скорость сходимости, чтобы увеличить скорость сходимости следует выбирать достаточно близкие значения интервала отделения корня , что при высокой скорости вычислений современных ПК не представляет больших затруднений.

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

Пример: уточнить корень уравнения , находящийся на методом простой итерации с точностью .

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

Проверяем принцип сжатых отображений для выбранной нами итерирующей функции (рассматриваем один из множества возможных способов представления итерирующей функции).

Проанализируем, как ведет себя функция на отрезке .

Построим таблицу

 

x	-1	-0,9	-0,8	-0,7	-0,6	-0,5	-0,4	-0,3	-0,2	-0,1	0
	1,818	1,587	1,367	1,158	0,96	0,773	0,596	0,431	0,276	0,133	0

 

Из таблицы видно, что концы отрезка, на котором выполняется условие , соответственно равны .

Таким образом будем уточнять корень на отрезке с помощью следующего рекуррентного уравнения

.

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

Сведем расчеты в таблицу

Таблица 5

№
1	-0,6	-0,45891	-0,766
2	-0,45891	-0,57568	0,642255
3	-0,57568	-0,48169	-0,51695
4	-0,48169	-0,5593	0,4268
5	-0,5593	-0,4964	-0,34597
6	-0,4964	-0,54822	0,285
7	-0,54822	-0,50606	-0,23188
8	-0,50606	-0,54074	0,19073
9	-0,54074	-0,51245	-0,15558
10	-0,51245	-0,53569	0,1278
11	-0,53569	-0,51671	-0,1044
12	-0,51671	-0,53229	0,0857
13	-0,53229	-0,51962	-0,069
14	-0,51962	-0,52994	0,057
15	-0,52994	-0,5215	-0,046

 

На 15 шаге выполняется условие выхода из итерационного процесса . Отсюда следует, что корень уравнения найденный по методу простой итерации с точностью равен .