Численные методы решения уравнений: классификация и итерации

2 Численные методы решения уравнений.
2.1 Классификация уравнений, их систем и методов решения.
Уравнения и системы уравнений делятся на:
1) алгебраические: уравнение называется алгебраическим, если над
неизвестными не совершается иных действий, кроме сложения, вычитания,
умножения, деления, возведения в степень и извлечения корня;
2) трансцендентные: уравнение называется если оно не является
алгебраическим, к трансцендентным уравнениям относятся логарифмические,
показательные, тригонометрические и т.д.
Алгебраические уравнения делятся на три типа:
1) целое алгебраическое уравнение: обе его части – целые алгебраические
выражения относительно неизвестных;
2) иррациональное уравнение: содержит под знаком корня алгебраическое
выражение относительно неизвестных;
3) дробное
(рациональное)
алгебраическое
уравнение:
содержит
в
числителе и знаменателе целое алгебраическое выражение относительно
неизвестных.
Решение дробных и иррациональных уравнений может быть сведено к
решению целых уравнений.
Уравнения и их системы могут быть линейными и нелинейными, в
зависимости от входящих в них операторов. Трансцендентные уравнения всегда
нелинейны, алгебраические уравнения могут быть как линейными так и
нелинейными.
Все методы решения уравнений можно разделить на
прямые
и
приближенные (итерационные) методы.
К прямым методам относятся методы Крамера, Гаусса, квадратного корня
и т. п. методы, основанные на операциях линейной алгебры.
Прямые методы могут, за редким исключением, применятся только к
линейным алгебраическим уравнениям. Приближенные методы применяются к
любым классам уравнений.
1
Ниже будут рассмотрены итерационные методы решения нелинейных
уравнений, которые также подходят и для решения линейных уравнений и их
систем.
2.2 Схема решения нелинейного уравнения.
Постановка задачи
Пусть имеется функция f(x), непрерывная на заданном отрезке. Требуется
найти корни уравнения
f(x) = 0
(2.1)
Пусть x* – истинное решение задачи (2.1).
Численное решение уравнения распадается на несколько подзадач:
1) Анализ количества, характера и расположения корней (обычно путем
построения графика функции или исходя из физического смысла исследуемой
модели). Здесь возможны следующие варианты:
− единственный корень;
− бесконечное множество решений;
− корней нет;
− имеется несколько решений, как действительных, так и мнимых
(например, для полинома степени n). Корни четной кратности выявить сложно.
2) Локализация корней (разбиение на интервалы) и выбор начального
приближения к каждому корню. В простейшем случае можно протабулировать
функцию с заданным шагом.
Теоретической основой отделения корней уравнения f (x)=0 является
вторая теорема Вейерштрасса: внутри отрезка [a, b] оси x имеется
единственный корень уравнения f (x) = 0, если:
a) функция f(x) непрерывна внутри отрезке [a, b];
b) на концах отрезка f(x) принимает значения разных знаков:
c) f'(x) знакопостоянна на отрезке [a, b], т.е. она имеет один и тот же знак.
Если в двух соседних узлах функция будет иметь разные знаки, то между
этими узлами лежит нечетное число корней уравнения (по меньшей мере один).
3) Вычисление каждого (или интересующего нас) корня уравнения с
требуемой точностью.
2
Пусть xi значение x на i-й итерации.
Погрешность (точность) вычисления корней уравнения (ε) можно задать
следующими способами:
1) абсолютным значением функции |f(xi)|;
2) разностью значений функции последней и предпоследней итераций |f(xi)
– f(xi – 1)|;
3) абсолютным значением приращения переменной за итерацию |xi – xi – 1|.
К математическому определению погрешности (|xi – x*|) ближе всего третий
способ, который является предпочтительным. Способы 1 и 2 применяются
гораздо реже.
2.3 Метод дихотомии (бисекций).
Также называется методом половинного деления.
Алгоритм поиска решения следующий:
1) задается начальный интервал [x0, x1], на котором f(x0)·f(x1) ≤ 0 (т.е. внутри
имеется не менее чем один корень);
2) находится точка x2 = 1/2 (x0 + x1) и вычисляется значение функции f(x2);
3) если f(x0)·f(x2) ≤ 0, для следующей итерации используется отрезок [x0, x2],
иначе – отрезок [x1, x2];
4) рассчитывается погрешность ε, если она выше заданной, деление пополам
продолжается (п. 2-3), если нет – решение считается найденным.
f1
f(x)
x0
x*
x1
x
f0
f2
Рисунок. 2.1. Пояснения к методу бисекции.
3
Скорость сходимости метода невысока, однако он прост и надежен. Метод
неприменим к корням четной кратности. Если на отрезке несколько корней, то
заранее неизвестно, к какому из них сойдется процесс.
Если на заданном интервале предполагается несколько корней, то
существует возможность последовательно исключать найденные корни из
рассмотрения. Для этого воспользуемся вспомогательной функцией g(x)=
f (x)
,
x− x̃
где x̃ – только что найденный корень. Для функций f(x) и g(x) совпадают все
корни, за исключением x̃ (в этой точке полюс функции g(x)). Для достижения
требуемой точности рекомендуется грубо приблизиться к корню по функции g(x),
а затем уточнить его, используя f(x).
2.4 Метод хорд.
Алгоритм поиска решения следующий:
1) задается начальный интервал [x0, x1], на котором f(x0)f(x1) ≤ 0;
2) строится хорда, соединяющая точки x0 и x1;
3) рассчитывается координата точки x2, где хорда пересекает ось абсцисс и
вычисляется значение функции f(x2);
4) если f(x0)f(x2) ≤ 0, для следующей итерации используется отрезок [x0, x2],
иначе – отрезок [x1, x2];
5) рассчитывается погрешность ε, если она выше заданной, итерации
продолжаются (п. 2-4), если нет – решение считается найденным.
f1
f(x)
x0
x2
x*
x1
x
f0
f2
Рисунок. 2.2. Пояснения к методу хорд.
4
Координата точки пересечения хорды с осью абсцисс находится из
уравнения прямой, проходящей через точки x0 и x1:
(2.2)
y=a x 2 +b=0
a=
f ( x 1)−f ( x 0)
x 1−x 0
(2.3)
b=f (x 0)−a x 0
x 2=x 0−
(2.4)
x 1−x 0
f (x 0 )
f (x 1 )−f (x 0)
(2.5)
Метод хорд в большинстве случаев сходится быстрее, чем метод
дихотомии. Недостатки метода те же, что и в предыдущем случае.
2.5 Метод Ньютона.
Также называется методом касательных.
Алгоритм поиска решения следующий:
1) задается начальное приближение x0;
2) рассчитывается значение функции f(x0) и строится касательная к функции
в этой точке;
3) рассчитывается координата точки x1, как координата пересечения
касательной и оси абсцисс;
4) рассчитывается погрешность ε, если она выше заданной, итерации
продолжаются (п. 2-3), если нет – решение считается найденным.
f0
f(x)
f2
x1
x*
x2 x0
x
f1
Рисунок. 2.3. Пояснения к методу Ньютона.
5
Уравнение касательной к функции f(x) в точке (xi, f(i):
y (x)=f ' ( x i )⋅( x−x i ) +f ( x i )
(2.6)
Отсюда координата следующей итерации:
x i+1=x i −
f ( xi )
(2.7)
f ' ( xi)
Итерационный процесс обладает абсолютной сходимостью если для всех x
выполняется условие:
∣(f (x)⋅f '' ( x ) )∣<( f ' ( x ) )
2
(2.8)
В противном случае сходимость будет не при любом начальном
приближении, а только в некоторой окрестности корня. Итерации будут
сходиться к корню с той стороны, где выполняется условие:
∣(f (x)⋅f '' ( x ) )∣⩾0
(2.9)
Метод обладает квадратичной сходимостью: погрешность очередного
приближения примерно равна квадрату погрешности предыдущего приближения.
Метод можно использовать для уточнения корней в области комплексных чисел,
что необходимо при решении многих прикладных задач, например при численном
моделировании электромагнитных колебательных и волновых процессов с учетом
временной и пространственной диссипации энергии.
Недостатком метода можно указать необходимость знать явный вид первой
и второй производных, так как их численный расчет приведет к уменьшению
скорости сходимости метода. Иногда, ради упрощения расчетов, используют т. н.
модифицированный метод Ньютона, в котором значение f'(x) вычисляется
только в точке x0, при этом число итераций увеличивается, но расчеты на каждой
итерации упрощаются.
2.6 Метод секущих.
Если в методе метода Ньютона заменить аналитическое значение
производной первой разностью, найденной по двум последним итерациям, т.е.
заменить касательную в точке секущей по двум последним точкам получится
метод секущих. В отличие от метода Ньютона в методе секущих задаются две
точки начального приближения как в методах бисекции и хорд.
Алгоритм поиска решения следующий:
6
1) задается начальный интервал [x0, x1];
2) строится секущая по точкам [x0, x1];
3) рассчитывается точка пересечения секущей с осью абсцисс, x2, и значение
функции f(x2);
4) рассчитывается погрешность ε, если она выше заданной, итерации
продолжаются (п. 2-3), если нет – решение считается найденным.
fi-1
fi+1
f(x)
xi
xi+1
x*
xi-1
x
fi
Рисунок. 2.4. Пояснения к методу секущих.
Итерационная формула имеет вид:
x i+1=x i −
( x i −x i−1 )⋅f ( x i )
f ( x i )−f ( x i−1 )
(2.10)
Сходимость может быть немонотонной даже вблизи корня. При этом вблизи
корня может происходить потеря точности, т.н. «разболтка решения», особенно
значительная в случае кратных корней. От разболтки осуществляется страхование
приемом Гарвика:
– задается максимально допустимая погрешность εmax, по абсолютному
значению приращения переменной за итерацию (метод 3), и ведется расчет до ее
достижения;
– продолжается расчет, пока погрешность убывает;
– расчет продолжается или по достижении требуемой точности ε, или при
возрастании погрешности на каком-либо шаге итерации, в этом случае в качестве
найденного решения применяется последняя итерация с невозрастающей
погрешностью.
7
Стоит заметить, что методы хорд и секущих схожи по применяемому
алгоритму, однако метод секущих не обладает абсолютной сходимостью и его
начальные точки могут находиться по одну сторону от искомого решения задачи
(2.1).
2.7 Метод простых итераций.
Если исходную задачу (2.1) заменить эквивалентной ей:
x= g( x)
(2.11)
Приходим к методу простых итераций.
Итерационная формула имеет вид:
x i+1=g(x i )
(2.12)
Алгоритм поиска решения методом простых итераций следующий:
1) задается начальное приближениеx0;
2) рассчитывается следующее приближение по формуле (2.12);
3) рассчитывается погрешность ε, если она выше заданной, итерации
продолжаются, если нет – решение считается найденным.
В самом простейшем случае имеем:
g(x)=f (x)+ x
(2.13)
Метод простых итераций абсолютно сходится если для всех x:
∣g '(x)∣<1
(2.14)
Метод Ньютона является частным случаем метода простых итераций,
обеспечивающий наибольшую скорость сходимости.
В качестве вывода по рассмотренным методам можно сказать, что наиболее
быстрой сходимостью обладает метод Ньютона, а методы хорд и дихотомии
обладают
абсолютной
сходимостью
при
условии
выполнения
теоремы
Веерштрасса.
2.8 Скорость сходимости численных методов решения уравнений.
Под скоростью сходимости итерационных численных методов понимают
скорость приближения решений, полученных на каждой итерации к истинному
решению задачи (2.1).
8
Для
количественной
оценки
скорости
сходимости
сравнивают
последовательность решений, полученных на каждой итерации с убывающей
геометрической прогрессий по зависимости:
∣x i −x*∣≤aqi
(2.15)
В этом случае скорость сходимости метода (p) рассчитывают из условия:
p
∣x i+1−x *∣≤a∣xi −x *∣
(2.16)
При этом a>0, p≥0 константы, не зависящие от x.
Если p = 1, то метод обладает линейной сходимостью в окрестности корня
x*, при
p > 1 метод обладает сверхлинейной сходимостью (при p = 2 –
квадратичной, p = 3 – кубической).
Метод
Таблица 2.1. Скорость сходимости наиболее популярных методов.
Скорость сходимости, p
Метод дихотомии
1
Метод секущих
1.62
Метод Ньютона
2
Метод Мюллера
1.84
Метод Чебышёва
3
Метод
обратной
интерполяции
параболической
1.8
Список литературы
1. Вержбицкий, В.М. Основы численных методов / В.М. Вержбицкий. – М.:
Высшая школа, 2002. – 840 с.
2. Амосов, А.А. Вычислительные методы для инженеров / А.А. Амосов, Ю.
А. Дубинский, Н.В. Копченова. – М.: Мир, 1998. – 544 с.
3. Бахвалов Н.С. Численные методы / Н.С. Бахвалов, Н.П. Жидков, Г.М.
Кобельков. – М.: Бином, 2004. – 634 с.
4. Корнюшин, П.Н. Численные методы / П.Н. Корнюшин. – Владивосток :
из-во Дальневосточного ун-та, 2002 . – 104 с.
9