Сравнительный анализ численных методов
Итерационные методы в этом отношении предпочтительнее. Они требуют хранения в памяти машины не всей матрицы системы, а лишь нескольких векторов с n компонентами. Погрешности окончательных результатов при использовании итерационных методов не накапливаются, поскольку точность вычислений в каждой итерации определяется лишь результатами предыдущей итерации и практически не зависит от ранее выполненных вычислений.
Применение итерационных методов для качественного решения СЛАУ требует серьёзного использования её структуры, специальных знаний и определённого опыта. Именно поэтому разработано большое число итерационных средств, каждый из которых ориентирован на решения сравнительно узкого числа задач, и существует довольно мало программ, реализующих эти методы. В курсе математического обеспечения САПР мы рассмаривали следующие итерационные методы решения СЛАУ: метод простой итерации, метод Зейделя.
3.1 Метод простой итерации
Этот метод широко используется для численного решения уравнений и их систем различных видов. Рассмотрим применение метода простой итерации к решению систем линейных уравнений.
Запишем
исходную систему
уравнений в
векторно-матричном
виде
,
где A- квадратная
невырожденная
матрица. Затем
необходимо
преобразовать
систему к виду
x=Bx+c,
где В- квадратная матрица с элементами bij (I,j=1,2,3…m) c- вектор-столбец с элементами ci (i=1,2,3…m)
В развёрнутой форме записи система имеет вид:
x1=b11x1+b12x2+b13x3+…b1mxm+c1
x2=b21x1+b22x2+b23x3+…b2mxm+c1
x3=b31x1+b32x2+b33x3+…b1mxm+c3
xm=bm1x1+bm2x2+bm3x3+…bmmxm+cm
Операция приведения системы к виду, удобному для итераций не является простой и требует специальных знаний. В некоторых случаях операция преобразования не имеет смысла, так как система бывает уже приведена к удобному для итераций виду.
Самым простым способом приведения системы к такому виду является тот, что описан ниже:
И первого уравнения системы выразим x1:
x1=a11-1(b1-a12x2- a13x3-…- a1mxm)
Из второго уравнения системы выразим x2:
x2=a22-1(b2-a21x2- a23x3-…- a2mxm)
xm=amm-1(bm-am1x2- am3x3-…- am-1mxm-1)
В результате получим систему:
x1=0+ b12x2+ b13x3-…+ b1m-1xm-1+ b1mxm+c1
x2= b21x2+0 +b23x3+…+ b2m-1xm-1+ b2mxm+c2
xm= bm1x1+ bm2x20 +bm3x3+…+ bmm-1xm-1+ 0+cm
в которой, на главной диагонали матрицы B находятся нулевые элементы, стальные элементы выражаются по формулам:
bij=-aij/aii ci=bi/aii (i,j=1,2,3…m, i<>j)
Итерационный процесс продолжается до тех пор , пока значения х1(k) , х2(k) , х3(k) не станут близкими с заданной погрешностью к значениям х1(k-1) , х2(k-1) , х3(k-1) .
Для возможности выполнения данного преобразования необходимо, чтобы диагональные элементы матрицы А были ненулевыми.
Часто систему
преобразуют
к виду x=x-
(Ax-b),
где
-специально
выбираемый
числовой параметр.
Описание метода:
Выберем начальное приближение x0=( x01 x02… x0m)
подставляя его в праву часть системы
x=Bx+c,
и вычисляя полученное выражение, находим первое приближение:
x1=Bx0+c
на втором шаге подставляем приближение x1 в правую часть той же системы, получим второе приближение:
x2=Bx1+c
Продолжая этот процесс далее, получим последовательность x1 x2 x3… xn приближений, вычисляемых по формуле :
![]()
Эта формула и выражает собой метод простой итерации.
Итерационный процесс продолжается до тех пор, пока значения х(k) не станут близкими с заданной погрешностью к значениям х(k-1).
Теорема. Метод
простой итерации
сходится тогда
и только тогда,
когда все собственные
числа матрицы
по модулю меньше
единицы, т.е.
либо
.Эти
выражения
являются условиями
сходимости
метода итераций
3.2 Метод Зейделя
Метод Зейделя можно использовать как модификацию метода простых итераций. Основная идея модификации состоит в том, что при вычислении очередного (k+1)-го приближения к известному xi при i>1 используют используются уже найденные приближения к известным x1,… xi-1, а не k-е приближение как в методе простых итераций.
На (k+1)-й итерации
компоненты
приближения
вычисляются
по формулам:
![]()
![]()
![]()
Условие сходимости метода Зейделя заключается в том, что матрица A системы Ax=b, должна удовлетворять условию:
модуль диагонального элемента должен быть больше суммы модулей оставшихся элементов строки или столбца.
Если данное условие выполнено, необходимо проследить, чтобы система была приведена к виду, удовлетворяющему решению методом простой итерации и выполнялось необходимое условие сходимости метода итераций:
,
либо
![]()
3.3 Практическое применение метода простых итераций для решения системы уравнений
Решим систему
линейных уравнений
методом простых
итераций с
точностью
равной
.

Выполним проверку на условие сходимости:


Условие выполнено, можно приступать к вычислению нулевого шага:
![]()
![]()
![]()
![]()
Начнем итерационный процесс, используя результаты начального приближения:
![]()
![]()
![]()
![]()
Проверим
выполняется
ли условие
остановки
итерационного
процесса:
:

Условие остановки на первом шаге итерации не было выполнено, поэтому продолжаем итерацию, вычисляя x(2) :
![]()
![]()
![]()
![]()
Проверим
выполняется
ли условие
остановки
итерационного
процесса:
:

Условие остановки на втором шаге итерации не было выполнено, поэтому продолжаем итерацию, вычисляя x(3) :
![]()
![]()
![]()
![]()
Проверим
выполняется
ли условие
остановки
итерационного
процесса:
:

Условие остановки на третьем шаге итерации было выполнено лишь для x4, поэтому продолжаем итерацию, вычисляя x(4) :
![]()
![]()
![]()
![]()
Проверим выполняется ли условие остановки итерационного процесса:
![]()

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

3.4 Практическое применение метода Зейделя для решения системы уравнений
Решим ту же
систему линейных
уравнений
методом Зейделя
с той же точностью
:
.

Проверку на условие сходимости мы выполнили ранее, при решении методом простых итерации.

![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
Проверим выполняется ли условие остановки итерационного процесса:
:

Условие остановки на первом шаге итерации не было выполнено, поэтому продолжаем итерацию, вычисляя x(2) :

Проверим выполняется ли условие остановки итерационного процесса:
:

Условие остановки на втором шаге итерации было выполнено лишь для x3, x4, поэтому продолжаем итерацию, вычисляя x(3) :

Проверим выполняется ли условие остановки итерационного процесса:
:

Условие сходимости выполнено на 3-ем шаге .
Корнями уравнения можно принять:

Как видно из вышеизложенных вычислений, скорость сходимости итерационного метода Зейделя выше, чем скорость сходимости метода простой итерации.
Ниже приведена сравнительная таблица1, позволяющая сравнить результаты решения СЛАУ методом простой итерации и методом Зейделя на различных шагах итерации:
Таблица1. Сводная таблица значений элементов приближений двух методов итерации
| № шага | Метод постой итерации | Метод Зейделя |
| 0 |
X1=1.04 X2=1.3 X3=1.45 X4=1.55 |
X1=1.04 X2=1.3 X3=1.45 X4=1.55 |
| 1 |
X1=0.75 X2=0.95 X3=1.14 X4=1.36 |
X1=0.75 X2=0.9674 X3=1.1976 X4=1.40402 |
| 2 |
X1=1.8106 X2=1.0117 X3=1.2117 X4=1.4077 |
X1=0.8019 X2=0.99956 X3=1.19956 X4=1.39999 |
| 3 |
X1=0.7978 X2=0.9977 X3=1.1975 X4=1.3983 |
X1=0.80006 X2=0.00002 X3=1.19999 X4=1.39997 |
| 4 |
X1=0.80046 X2=0.000502 X3=1.20052 X4=1.40034 |
3.5 Программная реализация итерационных методов

Рисунок 12. Решение системы уравнений методом простых итераций

Рисунок 13. Решение уравнения методом Зейделя
Раздел 4. Сравнительный анализ методов численного дифференцирования и интегрирования
4.1 Методы численного дифференцирования
Необходимость численного дифференцирования может возникнуть при необходимости исследований функций заданных табличным образом, кроме тех случаев, когда вычисление производной численно может оказаться проще, чем дифференцирование.
Предположим, что в окрестности точки xi функция F(x)дифференцируема достаточное число раз. Исходя из определения производной:
![]()
используем для её вычисления две приближенные формулы:
(1)
(2)
Формулы (1) и (2) называют правыми и левыми разностными производными.
Для оценки погрешностей формул численного дифференцирования используется формула Тейлора:
![]()
откуда можно вычислить:
(3)
Выражение (3) имеет погрешность порядка (x-xi), следовательно, формулы правых и левых разностных производных имеют погрешность одного порядка с h , где
h=xi-xi-1
Такая точность достаточно невысока, поэтому применяется так называемая центрально-симметричная форма производной, погрешность которой одного порядка с h2
(4)
Хотя очевидно, что формула (4) используется для внутренних точек отрезка.
Для примера возьмём ряд точек:
![]()
Вычислим производную функции f(x)=sin(x) в одной из них двумя способами.
Очевидно,
что h=![]()
По центрально-симметричной формуле:

По формуле левой разностной производной:

Табличное
значение
=cos(
)=0.8660
,т.е. значение
производной,
полученное
по центрально-симметричной
формуле ближе
к истинному.
4.2 Методы численного интегрирования
В прикладных исследованиях часто возникает необходимость вычисления значения определённого интеграла

Как известно из курса математики, аналитически вычисление интеграла можно провести не во всех случаях. И даже в том случае, когда удаётся найти аналитический вид этого интеграла, процедура вычисления даёт приближённый результат, поэтому возникает задача приближенного значения этого интеграла.
![]()
Суть приближенного вычисления заключается в двух операциях:
1. в выборе конечного числа вместо n
2. в выборе
точки
в соответствующем
отрезке.
В зависимости
от выбора
мы получаем
различные
формулы для
вычисления
интеграла:
Формулы левых и правых прямоугольников (5),(6)
(5)
(6)
Формула трапеции:
![]()
Формула Симпсона
![]()
где
m=n/2
h=b-a/n
b, a- концы рассматриваемого отрезка.
Для сравнения
результатов
вычисления
вышеизложенными
формулами
численного
интегрирования
вычислим 3-мя
способами
следующий
интеграл, разделив
отрезок [0,
]
на 6 равных отрезков:
h=![]()
По формуле левых прямоугольников:
![]()
По формуле трапеции:

По формуле Симпсона:

А результат полученный аналитически равен
=1
Следовательно, можно сделать вывод о том, что численный метод интегрирования по формуле Симсон является более точным, но используется в общем случае при делении рассориваемого отрезка на чётное число промежутков.
Раздел 5. Численные методы решения обыкновенных дифференциальных уравнений
Инженеру
часто приходится
иметь дело с
техническими
системами и
технологическими
процессами,
характеристики
которых непрерывным
образом меняются
во времени.
Соответствующие
явления как
правило подчиняются
физическим
законам, которые
формулируются
в виде дифференциальных
уравнений.
Одной из основных
математических
задач, которые
приходится
решать для
таких уравнений,
является задача
Коши (начальная
задача). Чаще
всего к ней
приходят тогда,
когда известно
начальное
состояние
физической
величины системы
в некоторый
момент времени
t0 (x0,y0) и требуется
предсказать
её поведение
в момент времени
t>t0 ( x>x0). В курсе
математического
обеспечения
САПР, мы рассматривали
методы решения
задачи Коши
с помощью решения
обыкновенного
дифференциального
уравнения
первого порядка
.
Напомним,
что решением
обыкновенного
дифференциального
уравнения (ОДУ)
первого порядка
является функция
y , которая при
подстановке
в уравнение
,
превращает
его в тождество.
Обыкновенными дифференциальными уравнениями называются такие уравнения, которые содержат одну или несколько производных от искомой функции y=y(x). Их можно записать в виде
,
где х – независимая переменная.
Наивысший
порядок n входящей
в уравнение
производной
называется
порядком
дифференциального
уравнения.
Методы решения обыкновенных дифференциальных уравнений можно разбить на следующие группы: графические, аналитические, приближенные и численные.
Графические методы используют геометрические построения.
Аналитические методы встречаются в курсе дифференциальных уравнений. Для уравнений первого порядка (с разделяющимися переменными, однородных, линейных и др.), а также для некоторых типов уравнений высших порядков (например, линейных с постоянными коэффициентами) удается получить решения в виде формул путем аналитических преобразований.
Приближенные методы используют различные упрощения самих уравнений путем обоснованного отбрасывания некоторых содержащихся в них членов, а также специальным выбором классов искомых функций.
Численные методы решения дифференциальных уравнений в настоящее время являются основным инструментом при исследовании научно-технических задач , описываемых дифференциальными уравнениями. При этом необходимо подчеркнуть , что данные методы особенно эффективны в сочетании с использованием современных компьютеров.
5.1 Метод Эйлера
Простейшим
численным
методом решения
задачи Коши
для ОДУ является
метод Эйлера.
Рассмотрим
уравнение
в окрестностях
узлов
(i=1,2,3,…) и заменим
в левой части
производную
правой разностью.
При этом значения
функции
узлах
заменим значениями
сеточной функции
:
![]()
Полученная аппроксимация ДУ имеет первый порядок, поскольку при замене
![]()
на
![]()
допускается
погрешность
.
Будем считать для простоты узлы равноотстоящими, т.е.
![]()
Тогда из равенства
![]()
получаем
![]()
Заметим, что из уравнения
![]()
следует
.
Поэтому
![]()
представляет
собой приближенное
нахождение
значение функции
в точке
при помощи
разложения
в ряд Тейлора
с отбрасыванием
членов второго
и более высоких
порядков. Другими
словами, приращение
функции полагается
равным её
дифференциалу.
Полагая i=0, с помощью соотношения
![]()
находим
значение сеточной
функции