Скачать

Численные методы

Теоретическая часть.

В данной расчетно-графической работе (далее РГР) требует-

ся составить программу для решения системы нелинейных уравне-

ний методом последовательной итерации обратной матрицы Якоби.

Суть метода в следующем:

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

или трансцендентных уравнений:

Fя41я0(Xя41я0,Xя42я0,...,Xя4nя0)=0; i=1,2,...,n,

с начальным приближением к решению:

Xя50я0=(xя41я50я0,xя42я50я0,...xя4nя50я0).

Вычислительная схема реализованного метода состоит в сле-

дующем:

В начале итерационного процесса матрица H полагается рав-

ной единичной:

Hя50я0=E.

Затем для k=0,1,...

1. Вычисляется

Pя5k я0=я5 я0-я5 я0Hя5k я0*я5 я0F(Xя5kя0);

2. Находятся

Xя5k+1 я0=я5 я0Xя5k я0+я5 я0tя5kя0*Pя5kя0.

Первоначально tя5kя0=1. Затем путем последовательного деления

- 2 -

tя5kя0 на 2 находим такое tя5kя0, чтобы выполнялось неравенство:

є F(Xя5k+1я0) є < є F(Xя5kя0) є

Итерационный процесс заканчивается при выполнении усло-

вия:

є F(Xя5k+1я0) є < E,

где E - заданная точность.

3. Определяется

Yя5kя0= F(Xя5k+1я0) - F(Xя5kя0)

4. Находится новое приближение матрицы:

Hя5k+1 я0=я5 я0Hя5k я0-я5 я0(Hя5kя0*Yя5k я0-я5 я0Pя5kя0*tя5kя0)я5 я0*я5 я0(Pя5kя0)я5T я0*я5 я0(Hя5kя0)я5T я0/я5 я0((Pя5kя0)я5T я0*я5 я0Hя5kя0*Yя5kя0)

и снова повторяется вычислительный процесс с пункта 1.

я2Порядок работы с программой

Данная РГР представлена в виде 3 исполняемых модулей:

я1OBRJ.M, OBRF.M и FUN1.M.я0 Решением поставленной задачи занима-

ется модулья1 OBRF.Mя0, а два остальных являются вспомогательными:

я1OBRJ.M -я0 головной модуль, в котором вводятся входные данные и

выводятся результаты вычислений, ая1 FUN1.M -я0 модуль, который

пишет сам пользователь и который возвращает вычисленные левые

части для требуемого уравнения.

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

- 3 -

виде вектора X0 а также запрашивается допустимая ошибка. Затем

вызывается модулья1 OBRJ.M,я0 который и реализует решение данной

системы уравнений методом последовательной итерации обратной

матрицы Якоби. Внутри себя данный модуль по мере необходимости

вызывает функциюя1 FUN1.Mя0, которую пишет сам пользователь.

я2Описание работы программ

В связи с тем, что данная РГР состоит из 3 частей, то

опишем их по одиночке (распечатки данных модулей приведены в

приложении):

1.я1 OBRJ.M

Головной модуль

Входные данные: отсутствуют.

Выходные данные: отсутствуют.

Язык реализации: PC MathLab.

Операционная система: MS-DOS 3.30 or Higher.

Пояснения к тексту модуля:

"Стандартный" головной модуль. В данном модуле задаются

начальные значения в виде вектора, например:

Xя40я0=(0.4 0.9)

Также в данном модуле запрашивается допустимая ошибка,

очищается экран, а также производятся другие подготовительные

действия.

Затем происходит вызов модуляя1 OBRF.Mя0 с полученными вход-

ными данными. Формат вызова данного модуля описан далее (в

описании самого модуля).

- 4 -

После вычислений в головную программу возвращаются ре-

зультаты вычислений на основе которых строятся графики а также

выводятся оценки по затратам машинного времени и быстродейс-

твия.

2.я1 OBRF.M

Вычислительный модуль

Входные данные:

FunFcn - имя функции, написанной пользователем, которая

вычисляет левые части для требуемой системы в определенной

точке.

X0 - вектор-строка, определяющий начальные значения (на-

чальное приближение).

E - допустимая ошибка.

Выходные данные:

Tout - Столбец итераций ("Время")

Xout - Столбцы значений вычисленных на каждом этапе для

каждой итерации

DXout - Столбцы погрешностей по каждой компоненте, вычис-

ленные на определенном этапе

Язык реализации: PC MathLab

Операционная система: MS-DOS 3.30 or Higher

Пояснения к тексту модуля:

Данный "вычислительный" модуль реализует метод последова-

- 5 -

тельной итерации обратной матрицы Якоби. Общая структура вызо-

ва данного модуля:

(Tя4outя0,Xя4outя0,DXя4outя0)=OBRF(FunFcn,Xя40я0,E);

Значения каждого из параметров были описаны выше.

На начальном этапе в данном модуле инициализируются внут-

ренние переменные (например, задается единичная матрица H, в

соответствии с размерностью X0), формируются (на основе на-

чальных значений) первичные элементы матриц Tout,Xout,DXout.

Затем данная функция, как и многие другие в численных методах,

имеет вид:

While ОШИБКА > ДОПУСТИМОЙ ОШИБКИ

Оператор1

Оператор2

.........

.........

ОператорN

End

Внутри данного цикла происходят вычисления внутренней пе-

ременной Pя5kя0 на каждом шаге K и, вычисляется начальное прибли-

жение Xя5k+1я0. Первоначально t=1 (Не номер итерации, а внутренний

параметр!). Затем, в очередном цикле While...End в случае, ес-

ли єF(Xя5k+1я0)є < єF(Xя5kя0)є t=t/2 и снова вычисляется Xя5k+1я0. Когда

очередное Xя5k+1я0 найдено, вычисляется Yя5kя0, а затем и новое приб-

лижение матрицы H. Итерационный процесс заканчивается, если

- 6 -

єF(Xя5k+1я0)є < E. Если данное условие не выполняется - итерацион-

ный процесс продолжается заново.

Формирование выходных значений-матриц происходит внутри

данного цикла и поэтому никаких дополнительных действий не

требуется, то есть с окончанием данного цикла заканчивается и

сама функция.

3.я1 FUN1.M

Модуль, вычисляющий левые части

Входные данные:

X - вектор-строка, задающий точки для вычислений по каж-

дой компоненте.

Выходные данные:

FF - вектор-строка, возвращающий значения каждой компо-

ненты в определенной точке

Язык реализации: PC MathLab

Операционная система: MS-DOS 3.30 or Higher

Пояснения к тексту модуля:

В принципе, текст данного модуля не требует пояснений. В

нем пользователь реализует систему уравнений, которая подлежит

решению. То есть на входные значения X данная функция возвра-

щает левые части по каждому уравнению. Единственное требование

к данному модулю - соблюдение формата, то есть входные и вы-

ходные данные должны быть представлены в виде вектор-строк.

я2Сравнительный анализ и

я2оценка быстродействия.

- 7 -

Сравнительный анализ показал, что данный метод обладает

неплохой сходимостью, так как попробованный метод простой ите-

рации с параметром вообще отказался сходиться для данной сис-

темы. Однако хорошо подходит для сравнения дискретный метод

Ньютона, так как данные методы практически одинаковы что по

точности что по затратам.

1. Метод последовательной итерации обратной матрицы Якоби

Число операций: порядка 682

Быстродействие: порядка 0.11 секунды

2. Метод Ньютона дискретный

Число операций: порядка 990

Быстродействие: порядка 0.22 секунды

Как видно из вышеприведенных данных, эти два метода очень

близки между собой, но метод Ньютона дискретный более сложен в

реализации, однако обладает лучшей сходимостью, например при

начальных значениях Xя50я0=(2.0 2.0); метод последовательной ите-

рации обратной матрицы Якоби уже не справляется, в то время

как дискретный метод Ньютона продолжает неплохо работать. Од-

нако метод Ньютона требует больших затрат машинного времени и

поэтому при выборе метода необходимо исходить их конкретных

условий задачи и если известно довольно точное приближение и

требуется быстрота вычислений, то к таким условиям отлично

подходит разработанный метод последовательной итерации обрат-

ной матрицы Якоби.

- 8 -

я2Выводы

В данной РГР был разработан и реализован метод последова-

тельной итерации обратной матрицы Якоби, предназначенный для

решения системы нелинейных уравнений. Программа, реализованная

на языке PC MathLab хотя и не является оптимальной, однако вы-

полняет поставленную задачу и решает системы уравнений. Реали-

зованный метод не отличается повышенной сходимостью и требует

довольно точного начального приближения, однако довольно быст-

ро сходится к точному решению, то есть его можно порекомендо-

вать для вычисления непростых систем нелинейных уравнений при

наличии довольно точного начального приближения и наличия вре-

менных ограничений.

я2Список литературы

1. О.М.Сарычева. "Численные методы в экономике. Конспект

лекций", Новосибирский государственный технический универси-

тет, Новосибирск 1995г.

2. Д.Мак-Кракен, У.Дорн. "Численные методы и программиро-

вание на Фортране", Издательство "Мир", М. 1977г.

3. Н.С.Бахвалов. "Численные методы", Издательство "Нау-

ка", М. 1975г.