Конспект лекций междисциплинарного курса МДК.01.04 Математические методы разработки алгоритмов профессионального модуля ПМ.01 Разработка программных модулей программного обеспечения для компьютерных систем (стр. 8 )

Представим матрицу A в виде произведения нижней треугольной матрицы L и верхней треугольной U.

Введем в рассмотрение матрицы

  и  

Можно показать, что A = LU. Это и есть разложение матрицы на множители.

После разложения матрицы на множители, решение системы сводится к последовательному решению систем с треугольными матрицами: и .

4.6. Итерационные методы решения СЛАУ

Решается система  Ax = b.

Для применения итерационных методов система должна быть приведена к эквивалентному виду x=Bx+d. Затем выбирается начальное приближение к решению системы уравнений

и находится последовательность приближений к корню.

Для сходимости итерационного процесса достаточно, чтобы было выполнено условие . Критерий окончания итераций зависит от применяемого итерационного метода.

4.6.1. Метод Якоби (метод простой итерации)

Самый простой способ приведения системы к виду удобному для итераций состоит в следующем: из первого уравнения системы выразим неизвестное x1, из второго уравнения системы выразим x2, и т. д. В результате получим систему уравнений с матрицей B, в которой на главной диагонали стоят нулевые элементы, а остальные элементы вычисляются по формулам:

, i, j = 1, 2, ... , n.

Компоненты вектора d вычисляются по формулам:

, i = 1, 2, ... , n.

Расчетная формула метода простой итерации имеет вид

,

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

, i = 1, 2, ... , m.

Критерий окончания итераций в методе Якоби имеет вид:

, где .

Если , то можно применять более простой критерий окончания итераций:

4.6.2. Метод Зейделя

Метод можно рассматривать как модификацию метода Якоби. Основная идея состоит в том, что при вычислении очередного (n+1)-го приближения к неизвестному xi при i >1 используют уже найденные (n+1)-е приближения к неизвестным x1, x2, ..., xi - 1, а не n-ое приближение, как в методе Якоби. Расчетная формула метода в покоординатной форме записи выглядит так:

, i = 1, 2, ... , m.

Условия сходимости и критерий окончания итераций можно взять такими же, как в методе Якоби.

5.  Численное интегрирование и дифференцирование

5.1. Постановка задачи численного интегрирования

При решении задач научного и инженерно-технического характера математическими методами часто возникает необходимость проинтегрировать какую-либо функцию. Есть функции, которые невозможно интегрировать аналитически, т. е. только в некоторых случаях по заданной функции можно найти первообразную. Общим способом интегрирования любых функций является численное интегрирование, методы которого в большинстве своем просты и легко переводятся на алгоритмические языки.

Геометрически интеграл функции f(x) в пределах от a до b представляет собой площадь криволинейной трапеции, ограниченной графиком этой функции, осью x и прямыми x = a и x = b.

Численные методы интегрирования используют замену площади криволинейной трапеции на конечную сумму площадей более простых геометрических фигур, которые могут быть вычислены точно. В этом смысле говорят об использовании квадратурных формул (по аналогии с задачей о квадратуре круга – построение квадрата с площадью, равной площади круга с определенным радиусом).

В большинстве методов используется приближенное представление интеграла в виде конечной суммы (квадратурная формула):

где ci – постоянные, называемые весами, а xi – принадлежат интервалу [a, b] и называются узлами.

В основе квадратурных формул лежит идея аппроксимации на отрезке интегрирования графика подынтегрального выражения функциями более простого вида, которые легко могут быть проинтегрированы аналитически и, таким образом, легко вычислены. Наиболее просто задача построения квадратурных формул реализуется для полиномиальных математических моделей.

Многочлен (полином) порядка n имеет вид

и определяется  значениями (n+1) констант ai. Если известно значение функции в (n+1) точках i = 0, 1, …, n, то данные параметры легко определяются из системы (n+1) линейных уравнений с (n+1) переменными ai

Если все xi различны, то данная система уравнений имеет единственное решение, так как определитель системы, составленный из коэффициентов системы линейных уравнений (так называемый определитель Вандермонда) будет отличен от нуля

Определив коэффициенты интерполяционного многочлена, можно легко вычислить приближенное значение интеграла, заменив подынтегральную функцию на полученный многочлен

Узлы интерполирования на отрезке интегрирования могут быть расположены на равном удалении друг от друга (эквидистантные узлы). В этом случае для полинома степени n имеем следующее

, , , ,

где h – шаг, xi – узлы интерполирования.

При n = 0 получаем метод прямоугольников. График функции f(x) на отрезке интегрирования заменяется на горизонтальную линию (полином степени 0).

5.2. Метод прямоугольников

Пусть функцию (рис. 5.1) необходимо проинтегрировать численным методом на отрезке [a, b]. Разделим отрезок на N равных интервалов (на рисунке N = 4).

Рис. 5.1. Геометрический смысл определенного интеграла

Площадь каждой из 4-х криволинейных трапеций можно заменить на площадь прямоугольника.  Ширина всех прямоугольников одинакова и равна

В качестве выбора высоты прямоугольников можно предложить выбрать значение функции на левой границе (метод левых прямоугольников). В этом случае высота первого прямоугольника составит f(a), второго – f(x1), третьего – f(x2), последнего – f(x3). Приближенное значение интеграла получается суммированием площадей прямоугольников:

Если в качестве выбора высоты прямоугольников взять значение функции на правой границе (метод правых прямоугольников), то в этом случае высота первого прямоугольника составит f(x1), второго – f(x2), третьего – f(x3), последнего – f(b):

Как видно, в этом случае, одна из формул дает приближение к интегралу с избытком, а вторая c недостатком. Можно предложить еще один способ, очевидно лучший, чем обе эти формулы – использовать для аппроксимации значение функции в середине отрезка интегрирования (метод центральных или средних прямоугольников):

В общем виде, если отрезок [a, b] разбить на N равных интервалов интегрирования  и к каждому интервалу применить формулу прямоугольников, то получим:

5.3. Метод трапеций

Использование для интерполяции полинома первой степени (прямая линия, проведенная через две точки) приводит к формуле трапеций. В качестве узлов интерполирования берутся концы отрезка интегрирования. Таким образом, криволинейная трапеция заменяется на обычную трапецию, площадь которой может быть найдена как произведение полусуммы оснований на высоту.

В случае N отрезков интегрирования для всех узлов, за исключением крайних точек отрезка, значение функции войдет в общую сумму дважды (так как соседние трапеции имеют одну общую сторону):