Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Пермский национальный исследовательский
политехнический университет
кафедра Технологии неорганических веществ
ЛАБОРАТОРНАЯ РАБОТА
ПО ИНФОРМАТИКЕ
МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ
Пермь 2012г.
Требования к выполнению лабораторной работы
Теоретические сведения
Решение нелинейных уравнений на заданном интервале проводится чаще всего численными (приближенными) методами.
Интервалом изоляции корня называется отрезок, на котором корень уравнения существует и единственный. Каждому корню соответствует свой интервал изоляции. Если корней несколько, то для каждого нужно найти интервал изоляции. Существуют различные способы нахождения интервала изоляции: аналитический, табличный, графический.
Табличный способ – это построение таблицы, состоящей из столбца аргумента x и столбца значений функции F(x). О наличии корней свидетельствуют перемены знака функции. Чтобы не произошло потери корней, шаг изменения аргумента должен быть достаточно мелким, а интервал изменения – достаточно большим.
Графический способ – это построение графика функции F(x) и определение числа корней по количеству пересечений графика с осью x. Ниже для иллюстрации графическим способом исследовано уравнение F(x) = 0,4 2x – 0,5x – 1 = 0.
На рис. 1.1 приведены построенные с помощью MathCAD графики функций F1(x) = 0,4 2x и F2(x) = 0,5x + 1. Корнями являются точки, в которых пересекаются два графика. Рисунок показывает, что исходное уравнение имеет два корня, расположенных на интервалах [–3, 0] и [0, 3].
Рис. 1.1 Графический способ нахождения интервалов изоляции
Пусть интервалы изоляции корней известны. Познакомимся с несколькими итерационными методами, позволяющими найти корень на известном интервале изоляции [a, b].
Метод деления отрезка пополам (дихотомии). Найдем середину отрезка [a, b]:
c = (a+b)/2.
Корень остался на одной из частей: [a, c] или [c, b]. Если F(a)F(с) < 0, то корень попал на отрезок [a, c], тогда деление отрезка можно повторить, приняв в качестве нового правого конца точку c, т.е. b = c. В противном случае корень попал на половину [c, b], и необходимо изменить значение левого конца отрезка: a = c. Поскольку корень всегда заключен внутри отрезка, итерационный процесс можно останавливать, если длина отрезка станет меньше заданной точности: |b – a| < .
На рис. 1.2 приведен текст программы MathCAD, реализующей метод дихотомии для решения уравнения F(x) = x2 – x – 1 = 0. Метод реализован в виде функции от аргументов a, b (концы интервала изоляции) и точности метода . Вызов этой функции при значениях a = –1, b = 0, = 0,01 дает значение корня – 0,617, при этом невязка уравнения, которую вычисляют, чтобы убедиться в правильности решения, равна –1,89210–3.
Рис. 1.2. Метод деления отрезка пополам
Метод хорд. В этом методе кривая F(x) заменяется прямой линией – хордой, стягивающей точки (a, F(a)) и (b, F(b)). В зависимости от знака выражения F(a)F(a) метод хорд имеет два варианта, изображенных на рис.1.3.
Пусть F(a)F(a)>0 (см. рис. 1.5а). Тогда x0 = b, точка a будет оставаться неподвижной. Следующее приближение x1 находим как точку пересечения хорды, соединяющей точки (a, F(a)) и (x0, F(x0)) с осью x. Уравнение хорды:
.
Тогда точка пересечения хорды с осью x:
.
Пусть теперь F(a)F(a) < 0 (рис. 1.5б). Тогда x0 = a, точка b неподвижна. Проведем хорду, соединяющую точки (b, F(b)) и (x0, F(x0)):
.
Вычисляем точку пересечения хорды с осью x:
.
На следующей итерации в качестве x0 надо взять вычисленное значение x1. Окончание итерационного цикла в этом методе происходит по условию малости невязки уравнения: |F(x1)| < .
Рис. 1.3. Метод хорд: а – F(a)F(a) > 0; б – F(a)F(a) < 0
Ниже представлен текст программы MathCAD решения уравнения методом хорд.
Рис. Листинг «решения уравнения методом хорд»
Метод Ньютона (касательных). Как и предыдущий, этот метод основан на замене исходного нелинейного уравнения линейным уравнением, которое можно легко решить. Иллюстрация метода представлена на рис. 1.4. Пусть x0 – начальное приближение. Построим касательную к функции y = F(x), проходящую через точку (x0, F(x0)).
Найдем пересечение касательной:
с осью x:
.
На следующей итерации в качестве x0 надо взять вычисленное значение x1. Окончание итерационного цикла, как и в методе хорд, выполняется по невязке уравнения: |F(x1)| < .
Рис. 1.4. Метод Ньютона
Как показывают практика и теоретические оценки, метод Ньютона позволяет достаточно быстро получить решение. Недостатком метода является то, что для некоторых функций F(x) при неудачном выборе начального приближения метод расходится. Ситуацию легко исправить, если выбрать x0 ближе к x*.
Ниже представлен текс программы MathCAD решения уравнения методом Ньютона с погрешностью ε 10-5.
Рис.
Упрощенный метод Ньютона. Эта модификация метода Ньютона используется, если производная F(x) представляет собой сложную функцию и для ее вычисления на каждой итерации требуется много времени. Зададим x0 – начальное приближение и вычислим производную z = F(x0). На следующих итерациях используется вычисленное значение производной:
.
Это упрощение несколько замедляет процесс сходимости к решению, однако сокращает время каждого итерационного цикла.
Метод Ньютона реализован в электронных таблицах Excel при использовании режима «Поиск решения». При решении уравнения 10x5-7=0 найден корень уравнения x=0,93 (рис. 1.5).
Рис. 1.5 Решение нелинейного уравнения методом «Поиска решения»
Метод секущих применяется, когда вычисление производной F(x) занимает много времени, а также если функция F(x) задана таблично. Для этого метода необходимо задать два начальных приближения: x0, x1, поэтому он называется двухшаговым (все рассмотренные выше методы были одношаговыми). Значение производной можно вычислить с помощью конечно-разностного соотношения
F(x1) .
Подставляя это соотношение в формулу для метода Ньютона, получим
.
На следующей итерации в качестве приближений x0, x1 возьмем уже вычисленные значения x1, x2, т.е. x0 = x1, x1 = x2, и будем вычислять новое приближение x2. Окончание итерационного цикла производится по невязке уравнения: |F(x2)| < e.
Для решения уравнения в MathCAD методом секущих служит функция root. Встроенная функция root в зависимости от типа задачи может иметь либо два аргумента: root (f(x), x), либо четыре аргумента: root (f(x), x, a, b). Здесь f(x) – скалярная функция, определяющая уравнение; x – скалярная переменная, относительно которой решается уравнение; a, b – границы интервала, внутри которого происходит поиск корня.
Первый тип функции root требует дополнительного задания начального значения переменной x. Для этого нужно просто предварительно присвоить x некоторое число. Поиск корня будет производиться вблизи этого числа. Таким образом, присвоение начального значения требует априорной информации о примерной локализации корня.
Рассмотрим решение уравнения sin(x) = 0, которое имеет бесконечное количество корней xN = N (N = 0, 1, 2, ...). Для поиска корня средствами MathCAD требуется его предварительная локализация путем задания начального приближения, например, x = 0.5. MathCAD находит с заданной точностью только один корень x0 = 0, лежащий наиболее близко к заданному начальному приближению. Если задать другое начальное значение, например, x = 3, то решением будет другой корень уравнения x1 = и т.д.
На рис. 1.6 приведен пример вызова стандартной функции root с двумя аргументами для нахождения корней уравнения sin(x) = 0, график функции f(x) = sin(x) и положение найденного корня.
Рис. 1.6 Использование стандартной функции root
для решения нелинейного уравнения sin(x) = 0
Если уравнение неразрешимо, то при попытке найти его корень будет выдано сообщение об ошибке. Кроме того, к ошибке или выдаче неправильного корня может привести и попытка применить метод секущих в области локального минимума или максимума f(x). В этом случае секущая может иметь направление близкое к горизонтальному, и выводить точку следующего приближения далеко от предполагаемого положения корня. Для решения таких уравнений лучше применять встроенную функцию Minerr. Аналогичные проблемы могут возникнуть, если начальное приближение выбрано слишком далеко от настоящего решения или f(x) имеет особенности типа бесконечности.
Иногда удобнее задавать не начальное приближение к корню, а интервал [a, b], внутри которого корень заведомо находится. В этом случае следует использовать функцию root с четырьмя аргументами, а начальное значение x присваивать не нужно. Поиск корня осуществляется в промежутке между a и b.
При этом явный вид функции f(x) может быть определен непосредственно в теле функции root. На рис. 1.7 приведен листинг программы с использованием этого варианта функции root.
Рис. 1.7. Поиск корня алгебраического уравнения в заданном интервале
Когда функция root имеет четыре аргумента, следует помнить о двух ее особенностях:
Если уравнение не имеет действительных корней, но имеет мнимые, то их также можно найти. На рис. 1.8 приведен пример, в котором уравнение x2 + 1 = 0, имеющее два чисто мнимых корня, решается два раза с разными начальными значениями.
Для решения этого уравнения второй вид функции root (с четырьмя аргументами) неприменим, поскольку f(x) является положительно опреде ленной и указать интервал, на границах которого она имела бы разный знак, невозможно.
Рис. 1.8. Поиск мнимого корня
Метод простой итерации (МПИ). Этот метод является обобщением всех описанных выше одношаговых методов. Слово «простой» означает, что для вычисления следующего приближения необходимо знать только одно предыдущее приближение. С помощью эквивалентных преобразований приведем исходное уравнение (1) к виду, удобному для применения метода простой итерации: x = (x). Выберем начальное приближение x0 [a, b]. Следующие итерации находим по формуле:
xk+1 = (xk).
Итерационный процесс заканчивается, если |(xk) – xk| < e или, что то же самое, |xk+1 – xk| < e. Иллюстра ция метода представлена на рис. 1.9.
Рис. 1.9. Сходящийся метод простой итерации:
а – (x) > 0; б – (x) < 0
Способ сведения исходного уравнения к виду x = (x) очень важен, поскольку от вида функции (x) зависит, будет ли итерационный процесс сходиться или нет.
Чтобы понять, каким условиям должна удовлетворять порождающая итерации функция (x), проведем некоторые теоретические оценки. Пусть xk – известное приближение, отличающееся от искомого корня на величину погрешности |xk – x*|. Следующее приближение xk+1 будет отличаться от корня на величину
|xk+1 – x*| = |(xk) – x*| = |(xk) – (x*)| = |()| |xk – x*|,
где – некоторая средняя точка отрезка (xk, x*).
Здесь использована теорема Лагранжа о конечном приращении, а также равенство x* = (x*), которое справедливо, поскольку x* – корень. В сходящихся методах каждое следующее приближение должно быть ближе к корню, чем предыдущее, а это справедливо, если |()| q < 1. Понятно, что чем меньше число q, тем быстрее сходится итерационный процесс. Можно получить оценку:
|xk+1 – x*| < q|xk – x*| < q2|xk–1 – x*| < … < qk|x0 – x*|.
Если удастся показать, что |xk+1 – x*| < q|xk – x*|a, a > 1, то говорят, что метод сходится с порядком a.
Можно доказать, что необходимым условием сходимости МПИ является |(x*)| < 1. Это условие трудно проверить, т.к. корень неизвестен. Но можно проверить более сильное достаточное условие сходимости МПИ |(x)| < 1, где x – любая точка некоторого отрезка [a, b], содержащего корень.
Проверим, выполняется ли необходимое условие метода Ньютона, для которого
.
Вычислим производную:
.
Следовательно, метод Ньютона всегда сходится в некоторой окрестности корня x*. Можно показать, что
|xk+1 – x*|<q|xk – x*|2,
т.е. a = 2: метод сходится со вторым порядком. Порядок сходимости метода Чебышева еще выше (a = 3), для метода секущих a = 1.67, а для метода дихотомии a = 1.
Если необходимое условие нарушается, то МПИ будет расходиться. Иллюстрация расходящихся итерационных методов приведена на рис. 1.10.
Рис. 1.10. Расходящийся метод простой итерации:
а – j¢(x) > 0; б – j¢(x) < 0
Таким образом, различают три вида сходимости:
- хорошая сходимость;
- удовлетворительная сходимость;
- плохая сходимость.
Ниже представлен расчет уравнения итерационным методом в Excel. При использовании итерационного аппарата электронной таблицы Excel необходимо отключить автоматический пересчет листа и ввести режим Итерации – вручную формулы с рекурсией (циклическими ссылками).
Рис. 1.11 Параметры вычисления итераций в электронной таблице Excel
Рис. 1.12 Метод простой итерации, реализованный в Excel,
в формате изображения формул и результатов
На рис. 1.12 представлен пример расчета уравнения 2x3+4x-9=0 методом простой итерации. Следует отметить, что начало итерирования характеризуется ФЛАГОМ расчета – ИСТИНА, а сам расчет ФЛАГОМ итерирования – ЛОЖЬ. Определено, что на 8-ой итерации достигается результат с погрешностью ε0,001, что является удовлетворительным результатом расчета.
Задания для самостоятельного выполнения
|
№ варианта |
Уравнение |
|
|
x-sin x = 0,25 |
|
|
tg(0,58x+0,1) = x2 |
|
|
|
|
|
tg(0,4x + 0,4) = x2 |
|
|
|
|
|
tg(0,5x+0,2) = x2 |
|
|
3x – cos x – 1 = 0 |
|
|
x – lg x = 0,5 |
|
|
5x – 6x – 3 = 0 |
|
|
x2 + 4 sin x = 0 |
|
|
ctg 1,05x – x2 = 0 |
|
|
2x + 5x – 3 = 0 |
|
|
x· lg x – 1,2 = 0 |
|
|
1,8 x2 - sin 10x = 0 |
|
|
|
|
|
tg(0,3x+0,4) = x2 |
|
|
x2 + 20 sin x = 0 |
|
|
|
|
|
tg(0,47x+0,2) = x2 |
|
|
x2 + 4 sin x = 0 |
|
|
|
|
|
2x – lg x – 7 = 0 |
|
|
|
|
|
3x - sin x - 1 = 0 |
|
|
|
|
|
x2 + 3 sin x = 0 |
|
|
e-2x – 2x + 1 = 0 |
|
|
x + lg x = 0,5 |
|
|
|
|
|
|
|
|
x3 – 3x2 + 9x – 8 = 0 |
|
|
x3 – 6x – 8 = 0 |
|
|
x3 + 0,2x2 + 0,5x – 2 = 0 |
|
|
x3 - 0,2x2 + 0,3x – 1,2 = 0 |
|
|
x3 - 0,1x2 - 0,4x – 1,5 = 0 |
|
|
x3 + x – 3 = 0 |
|
|
x3 + 3x2 + 12x + 3 = 0 |
|
|
x3 + 4x – 6 = 0 |
|
|
x3 + 0,2x2 + 0,5x + 0,8 = 0 |
|
|
x3 - 3x2 + 12x - 12 = 0 |
Сводная таблица результатов
|
Метод дихотомии (MathCAD) |
Метод хорд (MathCAD) |
Метод касательных (MathCAD) |
Метод Ньютона (Excel) |
Метод секущих (MathCAD) |
Метод простой итерации (Excel) |
|
|
Уравнение |
EMBED Mathcad