Система линейных алгебраических уравнений

Система линейных алгебраических уравнений

Система m линейных алгебраических уравнений с n неизвестными (или, линейная система, также употребляется аббревиатура СЛА́У) в линейной алгебре — это система уравнений вида

(1)

 

Система линейных уравнений от трёх переменных определяет наборплоскостей. Точка пересечения является решением.

Здесь   — количество уравнений, а   — количество неизвестных. x₁, x₂, …, x_n — неизвестные, которые надо определить. a₁₁, a₁₂, …, a_mn — коэффициенты системы — и b₁, b₂, …b_m — свободные члены — предполагаются известными^[1]. Индексы коэффициентов (a_ij) системы обозначают номера уравнения (i) и неизвестного (j), при котором стоит этот коэффициент, соответственно^[2].

Система (1) называется однородной, если все её свободные члены равны нулю (b₁ = b₂ = … = b_m = 0), иначе — неоднородной.

Система (1) называется квадратной, если число m уравнений равно числу n неизвестных.

Решение системы (1) — совокупность n чисел c₁, c₂, …, c_n, таких что подстановка каждого c_i вместо x_i в систему (1) обращает все её уравнения в тождества.

Система (1) называется совместной, если она имеет хотя бы одно решение, и несовместной, если у неё нет ни одного решения.

Совместная система вида (1) может  иметь одно или более решений.

Решения c₁⁽¹⁾, c₂⁽¹⁾, …, c_n⁽¹⁾ и c₁⁽²⁾, c₂⁽²⁾, …, c_n⁽²⁾ совместной системы вида (1) называются различными, если нарушается хотя бы одно из равенств:

c1(1) = c1(2), c2(1) = c2(2), …, cn(1) = cn(2).

Совместная система вида (1) называется определённой, если она имеет единственное решение; если же у неё есть хотя бы два различных решения, то она называется неопределённой. Если уравнений больше, чем неизвестных, она называется переопределённой

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

Прямые методы дают алгоритм, по которому можно найти точное решение СЛАУ. И если бы точность была абсолютной, они бы нашли его. Реальная ЭВМ, естественно, работает с погрешностью, поэтому решение будет приближённым.

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

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

• Метод Гаусса
• Метод Гаусса — Жордана
• Метод Крамера
• Матричный метод
• Метод прогонки (для трёхдиагональных матриц)
• Разложение Холецкого или метод квадратных корней (для положительно-определённых симметричных и эрмитовых матриц)
• Метод вращений^[3]

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

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

,

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

.

Итерационные методы делятся  на несколько типов, в зависимости  от применяемого подхода:

• Основанные на расщеплении: 
• Вариационного типа: 
• Проекционного типа: 

 

 

Аппроксимация производных

Напомним, что производной функции y=f(x) называется предел отношения приращения функции D y к приращению аргумента D x при стремлении D x к нулю:

. (1)

Обычно для вычисления производных используют готовые  формулы (таблицу производных) и  к выражению (1) не прибегают. Однако в численных расчетах на ЭВМ использование  этих формул не всегда удобно и возможно. В частности, функция y=f(x) может быть задана в виде таблицы значений. В таких случаях производную находят, опираясь на формулу (1). Значение шага D x полагают равным некоторому конечному числу и для вычисления значения производной получают приближенное равенство  

 

. (2)

Это соотношение  называется аппроксимацией (приближением) производной с помощью отношения конечных разностей (значения D y, D x в формуле (2) конечные в отличие от их бесконечно малых значений в (1)).

Рассмотрим аппроксимацию  производной для функции y=f(x), заданной в табличном виде: y₀, y₁,… при x = x₀, x₁,…. Пусть шаг - разность между соседними значениями аргумента - постоянный и равен h. Запишем выражения для производной   при x = x₁. В зависимости от способа вычисления конечных разностей получаем разные формулы для вычисления производной в одной и той же точке:

 (3)

с помощью левых разностей;

 (4)

с помощью правых разностей;

 (5)

с помощью центральных разностей. 

Можно найти также  выражения для старших производных. Например,

. (6)

Таким образом, по формуле (2) можно найти приближенные значения производных любого порядка. Однако при этом остается открытым вопрос о точности полученных значений.