Кафедра: АСОИиУ
Лабораторная Работа
На тему: НАХОЖДЕНИЕ КОРНЯ НЕЛИНЕЙНОГО УРАВНЕНИЯ. МЕТОДЫРЕШЕНИЯ СИСТЕМЫ НЕЛИНЕЙНЫХ УРАВНЕНИЙ
Москва, 2008 год
НАХОЖДЕНИЕ КОРНЯ НЕЛИНЕЙНОГО УРАВНЕНИЯ
1. Постановка задачи
Пустьзадана функция />, непрерывная вместе со своиминесколькими производными. Требуется найти все или некоторые вещественные корни уравнения
/>. (1)
Даннаязадача распадается на несколько подзадач. Во-первых, необходимо определитьколичество корней, исследовать их характер и расположение. Во-вторых, найтиприближенные значения корней. В-третьих, выбрать из них интересующие нас корнии вычислить их с требуемой точностью e. Первая и вторая задачи решаются, как правило,аналитическими или графическими методами. В случае, когда ищутся тольковещественные корни уравнения (1), полезно составить таблицу значений функции />. Если в двухсоседних узлах таблицы функция имеет разные знаки, то между этими узлами лежитнечетное число корней уравнения (по меньшей мере, один). Если эти узлы близки,то, скорее всего, корень между ними только один.
Найденныеприближенные значения корней можно уточнить с помощью различных итерационныхметодов. Рассмотрим три метода: 1) метод дихотомиии (или деление отрезкапополам); 2) метод простой итерации и 3) метод Ньютона.
2. Методы решения задачи
2.1 Метод деления отpезка пополам
Наиболеепростым методом, позволяющим найти корень нелинейного уравнения (1), является методполовинного деления.
Пустьна отрезке [a, b] задана непрерывная функция /> Если значения функции на концахотрезка имеют разные знаки, т.е. /> то это означает, что внутриданного отрезка находится нечетное число корней. Пусть для определенностикорень один. Суть метода состоит в сокращении на каждой итерации вдвое длиныотрезка. Находим середину отрезка [a,b] (см. рис. 1) /> Вычисляем значениефункции /> ивыбираем тот отрезок, на котором функция /> меняет свой знак. Новый отрезоквновь делим пополам. И этот процесс продолжаем до тех пор, пока длина отрезкане сравняется с наперед заданной погрешностью вычисления корня e. Построение несколькихпоследовательных приближений по формуле (3) приведено на рисунке 1.
Итак,алгоритм метода дихотомии:
1.Задать отрезок [a,b] и погрешность e.
2.Если f(a) и f(b)имеют одинаковые знаки, выдать сообщение о невозможности отыскания корня иостановиться.
/>
Рис.1.Метод деления отрезка пополам для решения уравнения вида f(х)=0.
3.В противном случае вычислить c=(a+b)/2
4.Если f(a) и f(c) имеютразные знаки, положить b=c, в противном случае a=c.
5.Если длина нового отрезка />, то вычислить значение корня c=(a+b)/2 и остановиться, в противном случае перейтик шагу 3.
Таккак за N шагов длина отрезка [a, b] сокращается в 2N раз, то заданная погрешность отыскания корня e будет достигнута за итераций.
/>
Каквидно, скорость сходимости мала, но к достоинствам метода относятся простота ибезусловная сходимость итерационного процесса. Если отрезок [a, b] содержит больше одного корня (но нечетное число), то всегдабудет найден какой-нибудь один.
Замечание. Для определения интервала, в котором лежит корень, необходимдополнительный анализ функции />, основанный либо на аналитическихоценках, либо на использование графического способа решения. Можно такжеорганизовать перебор значений функции в различных точках, пока не встретитсяусловие знакопеременности функции/>
2.2 Метод простой итерации
Прииспользовании этого метода исходное нелинейное уравнение (1) необходимопереписать в виде
/> (2)
Обозначимкорень этого уравнения C*. Пусть известно начальное приближениекорня />.Подставляя это значение в правую часть уравнения (2), получаем новоеприближение
/>
ит.д. Для (n+1)- шага получим следующее приближение
/> (3)
Такимобразом, по формуле (3) получаем последовательность С0, С1,…, Сn+1, которая стремиться к корню С*при n®¥. Итерационный процесс прекращается, если результаты двухпоследовательных итераций близки, т. е. выполняется условие
/> (4)
Исследуемусловие и скорость сходимости числовой последовательности {C n} при n®¥. Напомним определение скорости сходимости. Последовательность{Cn}, сходящаяся к пределу С*, имеет скоростьсходимости порядка a,если при n®¥выполняется условие
/> (5)
Допустим,что /> имеетнепрерывную производную, тогда погрешность на (n+1)-митерационном шаге en+1=Cn+1-C*=g(Cn)-g(C*) можно представить в виде ряда
en+1 » Cn+1 – C* = g¢(C*) (Cn-C*) +¼@ g¢(C*) en+¼
Такимобразом, получаем, что при выполнении условия
çg¢(C*) ç
последовательность(3) будет сходиться к корню с линейной скоростью a=1. Условие (6) является условием сходимости метода простой итерации. Очевидно,что успех метода зависит от того, насколько удачно выбрана функция />.
Например,для извлечения квадратного корня, т. е. решения уравнения вида x =a2,можно положить
x=g1(x)=a/x (7а)
или
x=g2(x)=(x+a/x)/2. (7б)
Нетруднопоказать, что
½g1'(C)½=1,
½g2'(C)½
Такимобразом, первый процесс (7а) вообще не сходится, а второй (7б) сходится прилюбом начальном приближении С0>0.
/>
Рис.2. Графическая интерпретация метода простых итераций для решения уравнения видаx=g(х).
Построениенескольких последовательных приближений по формуле (3)
С0,С1, …, Сn=C*
приведенона рисунке 2.
2.3 Метод Ньютона
Влитературе этот метод часто называют методом касательных, а также методомлинеаризации. Выбираем начальное приближение С0. Допустим, чтоотклонение С0от истинного значения корня С* мало, тогда,разлагая f(C*) вряд Тейлора в точке С0, получим
f(C*) = f(C0) + f ¢(C0) (C*-C0) +¼ (8)
Еслиf ¢(C0) ¹ 0, то в (8)можно ограничится линейными по DC =C-C0членами.Учитывая, что f(C*)=0,из (9) можно найти следующее приближение для корня
C1 = C0– f (C0) / f¢(C0)
илидля (n+1)-го приближения
Cn+1=C n – f (C n) / f ¢(C n) (9)
Дляокончания итерационного процесса можно использовать одно из двух условий
çCn+1 – Cnç
или
çf(Cn+1) ç
Исследованиесходимости метода Ньютона проводится аналогично предыдущему случаю.Самостоятельно получить, что при выполнении условия
½f ''(C)/2f'(C)½/>
методНьютона имеет квадратичную скорость сходимости (/>).
/>
Рис.3. Графическая интерпретация метода Ньютона для решения уравнения вида f(х)=0.
Построениенескольких последовательных приближений по формуле (9)
С0,С1, …, Сn=C*
приведенона рисунке 3.
Задание
1.Для заданной функции f(x)
· определите числовещественных корней уравнения f(x)=0, место их расположения и приближенные значения(постройте график или распечатайте таблицу значений).
· Вычислите один изнайденных корней (любой) с точностью e=0,5*10-3.
Длявычислений используйте метод деления отрезка пополам (определите числоитераций), а затем этот же корень найдите с помощью метода Ньютона (такжеопределив число итерационных шагов).
Сравнитеполученные результаты.
Варианты заданий
1.x3 –3x2 +6x – 5= 0 2. x 3 +sin x –12x-1=0
3. x3 –3x2 –14x – 8 = 0 4.3x + cos x + 1 =0
5. x2 +4sin x –1 = 0 6. 4x –ln x = 5
7. x6 –3x2 +x – 1 = 0 8.x3 – 0.1x2 +0.3x –0.6 = 0
9. /> 10. ( x -1)3 +0.5ex = 0
11. /> 12. x5–3x2 + 1 = 0
13. x3 –4x2 –10x –10 = 0 14./>
15. /> 16. />
17. /> 18. />
19. /> 20. />
21. /> 22. />
23. /> 24. x 4-2.9x3 +0.1x2 + 5.8x — 4.2=0
25.x4+2.83x3 — 4.5x2-64x-20=026. />
МЕТОДЫ РЕШЕНИЯ СИСТЕМЫ НЕЛИНЕЙНЫХ УРАВНЕНИЙ
1. Постановказадачи
Пустьтребуется решить систему n нелинейных уравнений:
/> (1)
Прямыхметодов решения системы (1) не существует. Лишь в отдельных случаях эту системуможно решить непосредственно. Например, для случая двух уравнений иногдаудаётся выразить одну неизвестную переменную через другую и таким образомсвести задачу к решению одного нелинейного уравнения относительно одногонеизвестного.
Системууравнений (1) можно кратко записать в векторном виде:
/>. (2)
Уравнение(2) может иметь один или несколько корней в области определения D. Требуетсяустановить существование корней уравнения и найти приближённые значения этихкорней. Для нахождения корней обычно применяют итерационные методы, в которыхпринципиальное значение имеет выбор начального приближения. Начальноеприближение иногда известно из физических соображений. В случае двухнеизвестных начальное приближение можно найти графически: построить наплоскости (x1,x2) кривые f1(x1, x2)=0 и f2(x1, x2)=0 и найти точки их пересечения. Длятрех и более переменных (а также для комплексных корней) удовлетворительныхспособов подбора начального приближения нет.
Рассмотримдва основных итерационных метода решения системы уравнений (1), (2) — методпростой итерации и метод Ньютона.
2. Методы решения системы нелинейных уравнений
2.1.Метод простой итерации
Представимсистему (1) в виде
/> (3)
илив векторной форме:
/> (4)
Алгоритмметода простой итерации состоит в следующем. Выберем некоторое нулевоеприближение
/>
Следующееприближение находим по формулам:
/>
илиболее подробно:
/> (5)
Итерационныйпроцесс (5) продолжается до тех пор, пока изменения всех неизвестных в двухпоследовательных итерациях не станут малыми, т.е.
/>
Напрактике часто вместо последнего условия используют неравенство:
/> (6)
где/>-среднеквадратичная норма n-мерноговектора />,т.е.
/>
Прииспользовании данного метода успех во многом определяется удачным выборомначального приближения />: оно должно быть достаточноблизким к истинному решению. В противном случае итерационный процесс может несойтись. Если процесс сходится, то его скорость сходимости является линейной.
2.2. Метод Ньютона
Впереводной литературе можно встретить название метод Ньютона-Рафсона. Этотметод обладает гораздо более быстрой сходимостью, чем метод простой итерации.
Пустьизвестно некоторое приближение /> к корню />, так что
/>
Тогдаисходную систему (2) можно записать следующим образом:
Разлагаяуравнение (7) в ряд Тейлора в окрестности точки /> и ограничиваясь линейными членамипо отклонению />, получим:
/>,
илив координатной форме:
/> (8)
Систему(8) можно переписать в виде:
/> (9)
Полученнаясистема (9) является системой линейных алгебраических уравнений относительноприращений
/>.
Значениефункций F1, F2, …, Fn и их производные в (9) вычисляютсяпри
/>.
Определителемсистемы (9) является якобиан J:
/> (10)
Длясуществования единственного решения системы уравнений (9) он должен бытьотличен от нуля. Решив систему (9), например, методом Гаусса, найдём новоеприближение:
/>.
Проверяемусловие (6). Если оно не удовлетворяется, находим /> и якобиан (10) с новымприближением и опять решаем (9), таким образом, находим 2-е приближение и т.д.
/>
Итерациипрекращаются, как только выполнится условие (6).
Задание
Используяметод Ньютона, найдите решения системы нелинейных уравнений с заданнойточностью />. Исследуйте сходимость итерационногопроцесса.
Варианты заданий
1/> 2/>
3/> 4/>
5/> 6/>
7/> 8/>
9/> 10/>
11/> 12/>
13/> 14./>
15./> 16. />
17./> 18. />
19./> 20./>
21./> 22./>