Численные методы
Теоретическая часть.
В данной расчетно-графической работе (далее РГР) требует-
ся составить программу для решения системы нелинейных уравне-
ний методом последовательной итерации обратной матрицы Якоби.
Суть метода в следующем:
Пусть требуется решить систему нелинейных алгебраических
или трансцендентных уравнений:
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г.