Методы компьютерных вычислений и их приложение к физическим задачам 2 (стр. 4 из 12)
Пусть
введена как интерполяционный многочлен Ньютона. В этом случае для произвольной неравномерной сетки: 
, для i = 0,1…n-1, интерполяция полиномом первой степени. 
, интерполяция полиномом второй степени.В общем случае
Минимальное число узлов, необходимое для вычисления k-й производной, равно k + 1.
Оценка погрешности при численном дифференцировании может быть осуществлена по формуле
где n – число узлов функции, k – порядок производной.
На практике чаще всего используются упрощенные формулы для равномерной сетки, при этом точность нередко повышается. Часто используются следующие формулы для трех узлов:
, где h = x1 – x0 = const. 
Исходя из общего вида интерполяционного полинома можно вывести формулы для более высокого порядка точности или для более высоких производных.
7. Численное решение систем линейных уравнений
Классы задач линейной алгебры
При численном решении большого круга задач в конечном итоге происходит их линеаризация, в связи с чем в соответствующих алгоритмах весьма широко используются методы линейной алгебры. В их числе:
· решение систем линейных алгебраических уравнений (СЛАУ);
· вычисление определителей матриц
;· нахождение обратных матриц
;· определение собственных значений и собственных векторов матриц
;Постановка задачи решения СЛАУ:
, (1)где
– квадратная матрица коэффициентов размерности n, 
– вектор неизвестных, 
– вектор свободных коэффициентов. Иногда СЛАУ представляют в виде расширенной матрицы размерности n × n+1, где в качестве последнего столбца фигурирует вектор свободных коэффициентов. В координатном представлении такая СЛАУ выглядит следующим образом: 
. (2)Для решения СЛАУ применяют в основном два класса методов: прямые (выполняемые за заранее известное количество действий) и итерационные (обеспечивающие постепенную сходимость к корню уравнения, зависящую от многих факторов). Прямые методы обычно применяются для решения систем порядка n < 200, для бóльших n используются итерационные методы. Перед решением СЛАУ требуется проанализировать корректную постановку задачи:
1) Если
– решение существует и единственно. Если же определитель равен нулю, то тогда, если матрица вырождена (т.е. ее можно преобразовать к виду, когда как минимум одна строка коэффициентов – нули) решений бесконечное множество, иначе решения не существует.2) Если
не имеет элементов с большими по модулю значениями решение устойчиво (см. пример к главе 1). Показателем плохо обусловленных систем является 
.Алгоритм метода Гаусса
1) Прямой ход.
Идея метода состоит в последовательном исключении неизвестных из системы n линейных уравнений. На примере первого уравнения системы (2) рассмотрим выражение для x1:
.Подставим выражение для x1 во второе и все остальные уравнения системы:
.Для расширенной матрицы коэффициентов это означает, что каждый элемент первой строки следует поделить на диагональный элемент, а все остальные строки преобразовать, как показано выше. Таким образом, станут равны нулю все коэффициенты первого столбца, лежащие ниже главной диагонали. Затем аналогичная процедура проводится со второй строкой матрицы и нижележащими строками, при этом первая строка и первый столбец уже не изменяются. И так далее до тех пор, пока все коэффициенты, лежащие ниже главной диагонали, не будут равны нулю.
Общие формулы прямого хода:
, (3)k = 1…n, j = 1…n+1. Звездочкой отмечены элементы k-й строки с измененными значениями, которые будут подставлены в следующую формулу. Для определенности будем считать первый индекс – по строкам, второй – по столбцам.
, (4)i = k +1…n, j = 1…n+1, k фиксировано в уравнении (3). Для уменьшения количества действий достаточно изменять значения элементов, находящихся выше главной диагонали.
2) Обратный ход.
Второй этап решения СЛАУ методом Гаусса называется обратным ходом и состоит в последовательном определении xk, начиная с xn, так как для последнего решение фактически получено. Общая формула:
. (5)Таким образом, вычисление корней
происходит за 2/3 n3 арифметических действий.3) Выбор главного элемента.
Для уменьшения погрешности вычислений следует стремиться к тому, чтобы на главной диагонали матрицы стояли максимальные по модулю значения коэффициентов. Алгоритмически этого можно добиться, переставляя строки таким образом, чтобы на диагонали стоял наибольший по модулю элемент текущего столбца. Такая процедура называется выбором главного элемента и осуществляется всякий раз при переходе к новой строке в прямом цикле метода Гаусса.
4) Погрешность метода. Расчет невязок.
Точность результатов будет определяться только точностью выполнения арифметических операций при преобразовании элементов матрицы, т.е. ошибкой округления. Контроль правильности полученного решения осуществляется подстановкой полученных значений x1…xn в исходную систему уравнений и вычислением невязок, т.е. разностей между правыми и левыми частями уравнений:
, где k = 1…n. (6)Специально отметим, что подставлять найденные значения
следует в исходную (не преобразованную к верхнетреугольному виду) систему.5) Преимущества и недостатки метода.
Преимущество метода в том, что он позволяет достичь результата за заранее известное и фиксированное число действий. Точность результатов будет определяться правильным выбором порядка коэффициентов в матрице
и ее размерностью. Недостатком метода является резкое увеличение времени и погрешности вычислений с ростом n.Блок-схема алгоритма метода Гаусса без выбора главного элемента
Итерационные методы решения систем линейных уравнений.
Простейшим итерационным методом решения СЛАУ является метод простой итерации. При этом система уравнений
(1) преобразуется к виду 
(2)а ее решение находится как предел последовательности
(3)где {n} – номер итерации. Утверждается, что всякая система (2), эквивалентная (1), записывается в виде
Теорема о достаточном условии сходимости метода простой итерации утверждает, что если норма матрицы
( 
)то система уравнений (2) имеет единственное решение и итерационный процесс (3) сходится к решению со скоростью геометрической прогрессии.
Теорема о необходимом и достаточном условии сходимости метода простой итерации: Пусть система (2) имеет единственное решение. Итерационный процесс (3) сходится к решению системы (2) при любом начальном приближении тогда и только тогда, когда все собственные значения матрицы
по модулю меньше 1.