15.1.Основні задачі числових методів алгебри.

Методы решения

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

Прямые методы:

Метод Гауса

Пусть исходная система выглядит следующим образом

Матрица A называется основной матрицей системы, b — столбцом свободных членов.

Тогда согласно свойству элементарных преобразований над строками основную матрицу этой системы можно привести к ступенчатому виду(эти же преобразования нужно применять к столбцу свободных членов):

Метод Крамера (правило Крамера) — способ решения квадратных систем линейных алгебраических уравнений с ненулевым определителем основной матрицы (причём для таких уравнений решение существует и единственно)

Для системы n линейных уравнений с n неизвестными (над произвольным полем)

с определителем матрицы системы Δ, отличным от нуля, решение записывается в виде

(i-ый столбец матрицы системы заменяется столбцом свободных членов).

В другой форме правило Крамера формулируется так: для любых коэффициентов c1, c2, …, cn справедливо равенство:

В этой форме формула Крамера справедлива без предположения, что Δ отлично от нуля, не нужно даже, чтобы коэффициенты системы были бы элементами целостного кольца (определитель системы может быть даже делителем нуля в кольце коэффициентов). Можно также считать, что либо наборы b1,b2,...,bn и x1,x2,...,xn, либо набор c1,c2,...,cn состоят не из элементов кольца коэффициентов системы, а какого-нибудь модуля над этим кольцом. В этом виде формула Крамера используется, например, при доказательстве формулы для определителя Грама и Леммы Накаямы.

Ма́тричный метод решения систем линейных алгебраических уравнений с ненулевым определителем состоит в следующем.

Пусть дана система линейных уравнений с n неизвестными (над произвольным полем):

Тогда её можно переписать в матричной форме:

AX = B, где A — основная матрица системы, B и X — столбцы свободных членов и решений системы соответственно:

Умножим это матричное уравнение слева на A - 1 — матрицу, обратную к матрице A: Так как A − 1A = E, получаем X = A - 1B. Правая часть этого уравнения даст столбец решений исходной системы. Условием применимости данного метода (как и вообще существования решения неоднородной системы линейных уравнений с числом уравнений, равным числу неизвестных) является невырожденность матрицы A. Необходимым и достаточным условием этого является неравенство нулю определителя матрицы A:

Для однородной системы линейных уравнений, то есть когда вектор B = 0, действительно обратное правило: система AX = 0 имеет нетривиальное (то есть ненулевое) решение только если detA = 0. Такая связь между решениями однородных и неоднородных систем линейных уравнений носит название альтернативы Фредгольма.

Итерационные методы

Метод Ньютона (метод касательных): Одномерный случай. Для того, чтобы решить уравнение пользуясь методом простой итерации, необходимо привести его к виду где — сжимающее отображение. Чтобы отображение было наиболее эффективно, необходимо, чтобы в точке очередной итерации x * выполнялось

удем искать решение данного уравнения в виде:

Воспользуемся тем, что и получим окончательную формулу для С учётом этого сжимающая функция примет вид: Тогда алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления: