МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИРОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕУЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ«НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
Кафедра экономической информатики
Курсовая работа
по дисциплине «Численные методы»
на тему: «Исследование метода простойитерации и метода Ньютона для решения систем двух нелинейных алгебраическихуравнений»
Выполнил
Студент: Обухова Т.С.
Факультет ФБ
Группа ФБИ-72
Преподаватель: СарычеваО.М.
Новосибирск
2009
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1 Постановка задачи. Математическоеописание методов
1.1 Метод простой итерации
1.2 Метод Ньютона
2 Описание программного обеспечения
3 Описание тестовых задач
4 Анализ результатов, выводы
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
ВВЕДЕНИЕ
Очень часто в различныхобластях экономики приходится встречаться с математическими задачами, длякоторых не удается найти решение классическими методами или решения выраженыгромоздкими формулами, которые не приемлемы для практического использования.Поэтому большое значение приобрели численные методы. В большинстве случаевчисленные методы являются приближенными, так как с их помощью обычно решаютсязадачи, аппроксимирующие исходные. В ряде случаев численный метод строится набазе бесконечного процесса, который в пределе сводится к искомому решению.Однако реально предельный переход не удается осуществить, и процесс, прерванныйна некотором шаге, дает приближенное решение. Кроме того, источникамипогрешности являются несоответствие математической модели изучаемому реальномуявлению и погрешность исходных данных.
Решение систем нелинейныхалгебраических уравнений – одна из сложных и до конца не решенных задач. Даже орасположении и существовании корней систем нелинейных уравнений почти ничегонельзя сказать. Большинство методов решения систем нелинейных уравненийсходятся к решению, если начальное приближение достаточно близко к нему, имогут вообще не давать решения при произвольном выборе начального приближения.Условия и скорость сходимости каждого итерационного процесса существеннозависят от свойств уравнений, то есть от свойств матрицы системы, и от выбораначальных приближений.
Численный метод, вкотором производится последовательное, шаг за шагом, уточнение первоначальногогрубого приближения решения, называется итерационным. Итерационные методы даютвозможность найти решение системы как предел бесконечного вычислительногопроцесса, позволяющего по уже найденным приближениям к решению построитьследующее, более точное приближение. Плюсом таких методов являетсясамоисправляемость и простота реализации на ЭВМ. В точных методах ошибка ввычислениях приводит к накопленной ошибке в результате, а в случае сходящегосяитерационного процесса ошибка в каком-либо приближении исправляется впоследующих итерациях, и такое исправление требует, как правило, тольконескольких лишних шагов единообразных вычислений. Для начала вычисленийитерационных методом требуется знание одного или нескольких начальныхприближений к решению.
В данной курсовой работенеобходимо рассмотреть два из множества существующих итерационных методов — метод простой итерации и метод Ньютона (классический) для решения системлинейных алгебраических уравнений.
1 Постановка задачи. Математическоеописание методов
При определенных условияхЭО в установившемся режиме описывается системой нелинейных АУ вида. Если приэтом входной сигнал /> известен, то для определениясоответствующего значения /> необходимо решить системунелинейных АУ вида:
/>(1)
Которая в нашем случаепредставляет собой систему из двух нелинейных уравнений с двумя неизвестнымивида:
/>(2)
Обобщенный алгоритмрешения системы (1) определяется формулой
/>,
где:
G – вектор-функция размерности n, которая определяется способомпостроения итерационного процесса;
p – количество предыдущих точекзначений X, используемых в данном итерационномпроцессе.
Если в итерационномпроцессе используется только одна предыдущая точка (p=1), то
/>
Рассмотрим подробнее дватаких метода – метод простой итерации и метод Ньютона.
1.1 Метод простой итерации
Пусть дана система (2),корни которой требуется найти с заданной точностью.
Предположим, что системадопускает лишь изолированные корни. Число этих корней и их приближенныезначения можно установить, построив кривые /> и /> и определив координаты их точек пересечения (либо изсуществующих представлений о функционировании экономического объекта).
Для применения методаитераций система (2) приводится к виду
/> (3)
Функции /> и /> называются итерирующими. Алгоритм решения задаетсяформулами:
/> (n=0, 1, 2, …),
где /> - некоторое начальное приближение.
Для приведения системы(2) к виду (3) используем следующий прием. Положим
/> (/>). (4)
Коэффициенты /> найдем как приближенные решения следующей системыуравнений:
/>
Характеристики метода:
1. Сходимость.
Локальная, то есть методсходится при выборе начальных приближений достаточно близко к точному решению.Насколько близко необходимо выбирать начальное приближение, исследуем впрактической части.
2. Выбор начальногоприближения
Начальные значенияпеременных должны выбираться близко к точным.
3. Скорость сходимостилинейная.
4. Критерий окончанияитераций.
Определяется по формуле:
/>,
1.2 Метод Ньютона
Пусть дана система (2).Согласно методу Ньютона последовательные приближения вычисляются по формулам
/>
Где
/>, />,
а якобиан
/>
Характеристики метода:
1. Сходимость.
Локальная, то есть методсходится при выборе начальных приближений достаточно близко к точному решению.Насколько близко необходимо выбирать начальное приближение, исследуем впрактической части.
2. Выбор начальногоприближения
Начальные значенияпеременных должны выбираться близко к точным.
3. Скорость сходимостиквадратичная.
4. Критерий окончанияитераций.
Аналогично методу простойитерации:
/>,
2 Описание программного обеспечения
метод итерация ньютоннелинейное уравнение
Программное обеспечениепредставлено в виде двух основных модулей – mpi2.m(метод простой итерации) и kmn2.m (классический метод Ньютона) и трехвспомогательных модулей – funF.m (матрица системы), funJ.m (матрица Якоби для системы), head.m(головная программа).
Головная программа –модуль head.m
Используемыепеременные:
x– вектор начальных приближений;
edop – допустимая ошибка вычислений;
Текстпрограммы:
/>
Исходная системауравнений – модуль funF.m
Входные параметры:
x – вектор — текущее приближение крешению;
Выходные параметры:
F – вектор значений функции, полученныхв точке x
Текст программы:
function [F]=funF(x)
F=[/>; />];
В векторе содержатсяфункции F1 и F2 по строкам.
Матрица Якоби – модуль funJ.m
Входные параметры:
x – вектор — текущее приближение крешению;
Выходные параметры:
J – матрица Якоби, полученная в точке x
Текст программы:
function[j]=funJ(x)
j=[/> />;
/> />];
В матрице содержатсячастные производные функций F1 и F2 по x1 и x2.
Метод простой итерации –модуль mpi2.m
Входные параметры:
x– вектор начальных приближений;
edop – допустимая ошибка вычислений;
Используемыепеременные:
F – вектор функции, полученный внекоторой точке;
J – матрица Якоби, вычисленная отначальных условий;
dx — вектор ошибки на каждом шагеитерационного процесса;
alpha, beta, gamma, delta – параметры используемые дляприведения системы (2) к виду (3);
nf, ndx – нормы вектора функции и вектораошибки соответственно;
x — вектор решения системы на каждомшаге итерационного процесса.
Выходные параметры:
xout–матрица размерности n×2значений решения системы, составленная по строкам из решений на m-номшаге;
dxout–матрица размерности n×2значений ошибки решения, составленная по строкам из ошибок на m-номшаге;
mout – вектор, составленный из номеровитераций на каждом шаге.
Текстпрограммы:
/>
Классический метод Ньютона – модуль mpi2.m
Входные параметры:
x– вектор начальных приближений;
edop – допустимая ошибка вычислений;
Используемыепеременные:
F – вектор функции, полученный внекоторой точке;
J – матрица Якоби, вычисленная внекоторой точке;
dx — вектор ошибки на каждом шагеитерационного процесса
delta – вектор промежуточных значений,используемых для расчета dx
nf, ndx – нормы вектора функции и вектораошибки соответственно;
x — вектор решения системы на каждомшаге итерационного процесса.
Выходные параметры:
xout–матрица размерности n×2значений решения системы, составленная по строкам из решений на m-номшаге;
dxout–матрица размерности n×2значений ошибки решения, составленная по строкам из ошибок на m-номшаге;
mout – вектор, составленный из номеровитераций на каждом шаге.
Текстпрограммы:
/>
3 Описание тестовых задач
В данной работе спроектированы программа,реализующие методы простой итерации и Ньютона применительно к решению системнелинейных уравнений. Для проверки предлагается решение системы уравнений споследующим исследованием рассматриваемых методов на её примере. При этомисследуется влияние вектора начального приближения к решению и значениядопустимой ошибки на сходимость методов и число итераций.
1. Решение системы /> обеими методами, графики решений и ошибок приначальных условиях />:
/>
/>
Как и следовало ожидать,метод Ньютона сошелся на две итерации быстрее благодаря квадратичной скоростисходимости.
2. При начальных условиях /> - начальные условия отстоят от точного решенияпримерно на 0,5.
/>
/>
Метод Ньютона опятьсошелся быстрее на две итерации, общее число итерации каждого метода посравнению с предыдущим решением увеличилось на единицу, поэтому можно сделатьвывод, что разница между точным решением и начальным приближением 0,5несущественно повлияла на сходимость.
3. При начальных условиях /> - начальные условия отстоят от точного решенияпримерно на 2.
Результаты вычисленийпоказывают, что при отстоянии начального приближения от точного значения на 2количество итераций в методе простой итерации значительно возросло, в то времякак число итерации метода Ньютона увеличилось всего на 1.
4. Для проверки времени счета введем вмодули методов новую переменную t,определяющую время счета, и возьмем начальные приближение, очень далекие отточного решения /> - начальные условия отстоят от точного решенияпримерно на 37.
/>/>
/>
/>
/>
Время в MatLab выводится в форматегод/месяц/день/часы/минуты/секунды, то есть метод простой итерации сошелся за0,015 секунд, а метод Ньютона за время менее 0,00009 секунд (не отображается);число итераций метода простой итерации возросло на 200, метода Ньютона – наединицу. Так как из теории известно, что если метод Ньютона не сходится за 6-7итераций, то он не сойдется вообще, попытаемся найти такое начальноеприближение, при котором этот метод уже не сойдется.
При начальных условиях x0=[1000;500]; edop=0.01 метод итераций сходится ужеболее чем за минуту и 44 тысячи итераций, а метод Ньютона – за неотображаемоевремя и 15 итераций. Таким образом, метод итераций хоть и сходится, но требуетнеадекватных эффективности вычислительных затрат, а метод Ньютона, несмотря натеорию о его несходимости при количестве итераций больше 6-7, сходится, и оченьбыстро.
Возьмем начальные условияx0=[10000000000; 1500000000], edop=0.01 и решим систему методом Ньютона.
t =0 0 0 0 0 0.0160
То есть метод сошелся за0,016 секунд, выполнив при этом 35 итераций, и все еще сходится.
Увеличивая начальноеприближения до величины порядка 1040, мы все еще получаемсходимость, при количестве итераций порядка 130.
4 Анализ результатов, выводы
Целью нашего исследованиебыло сравнение методов простой итерации и Ньютона для решения систем из двухнелинейных уравнений по числу итераций, времени сходимости в зависимости отвыбора начального приближения к решению и допустимой ошибки. Зависимость этихпараметров от выбора начального приближения подробно представлена в предыдущемпункте. Проанализировав полученные результаты, можно сказать, что придостаточном удалении от точного решения количество итераций и время счета обоихметодов, безусловно, возрастает, но в случае метода простой итерации количествоитерации возрастает геометрически относительно метода Ньютона. Мы попыталисьопределить границы сходимости метода Ньютона, но многократные расчеты придостаточно больших начальных приближениях (порядка 1040) не смоглидать ответа на этот вопрос – точное решение достигалось за очень малое (всравнении со степенью приближений) число итераций – порядка 130.
Сравнив методы по временисчета и количеству итераций при различной точности (в данной работе наглядно непредставлено), можно сделать вывод, что метод Ньютона и по этому параметруэффективней метода простой итерации – при допустимой ошибке 10-14метод простой итерации сошелся за 235 итераций и 0,016 секунд, а метод Ньютона– за 7 итераций и неотобразимо малое время.
Таким образом, сделаемобщий вывод: метод Ньютона на порядок эффективней метода простой итерации потаким параметрам, как время счета и число итераций при выборе начальногоприближения, достаточно далекого от точного решения или при достаточно высокойточности вычислений.
ЗАКЛЮЧЕНИЕ
При выполнении даннойработы были рассмотрены теоретически и практически основные характеристикиметодов простой итерации и Ньютона для решения систем двух нелинейныхуравнений.
Мы получили следующиерезультаты:
· метод простойитерации проще в реализации, чем метод Ньютона – он не требует, в частности,расчета матрицы Якоби на каждом шаге;
· методы сходятсяза небольшое количество итераций, если начальное приближение взято близко кточному решению;
· при отдаленииначального приближения от точного решения, скорость сходимости и число итерацийметодов отличаются на порядки, метод Ньютона сходится за гораздо меньшее времяи число итераций;
· при очень сильномотдалении от начального решения применение метода простой итерациинецелесообразно ввиду очень больших вычислительных затрат;
· при уменьшениидопустимой ошибки вычислительные затраты метода простой итерации значительнобольше, чем метода Ньютона, но не так велики, как при увеличении начальныхприближений на тот же порядок – то есть изменение точности имеет меньшее влияниена параметры сходимости, чем изменение начального приближения;
Метод Ньютона для решениясистем двух нелинейных уравнений оказался более эффективным, чем метод простойитерации по всем рассматриваемым параметрам.
Нам не удалось определитьмерность начального приближения, необходимого для того, чтобы метод Ньютона несошелся.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Копченова Н.В.,Марон И.А. Вычислительная математика в примерах и задачах.–М.: Наука, 1972. –368 с.
2. Сарычева О.М.Численные методы в экономике: Конспект лекций /НГТУ –Новосибирск, 1995. – 65 с.
3. Ортега Дж., Рейнболдт В. Итерационныеметоды решения нелинейных систем уравнений со многими неизвестными. – М.: Мир,1975. – 558 с.