Кафедра физхимии ЮФУ (РГУ)

ЧИСЛЕННЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ

Материалы к лекционному курсу

Лектор – ст. преп. Щербаков И.Н.

Системы линейных уравнений

Системы n линейных уравнений с n неизвестными x₁, x₂, ..., x_n в общем случае принято записывать следующим образом:

где а_ij и b_i – произвольные константы. Число n неизвестных называется порядком системы.

Решением уравнения является такая совокупность значений переменных х₁, х₂,…, х_n, которая одновременно обращает все уравнения системы в тождество.

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

Эквивалентной (и весьма удобной!!!) записью системы линейных уравнений является матричная запись

или сокращенно ,

в чем легко убедится, если воспользоваться правилами перемножения матриц: элемент, стоящий на пересечении i-й строки и j-го столбца матрицы-результата есть скалярное произведение i-й вектор-строки первой матрицы и j-го вектор-столбца второй матрицы.

Коэффициенты при неизвестных образуют квадратную матрицу размером n x n, (A), переменные и свободные члены уравнений – векторы-столбцы длиной n (Х) и (В), соответственно.

Решение системы уравнений есть вектор (X^*), который обращает это матричное уравнение в тождество.

Для решения системы линейных уравнений применяются точные методы (прямые) в которых количество арифметических, необходимых для нахождения решения, операций точно определяется порядком системы и итерационные (приближенные) методы, в которых проводится пошаговое, итерационное уточнение решения.

Оценить близость какого-либо вектора (Х)_i к решению системы уравнений можно оценив близость вектора невязок , вычисляемого приведенным ниже образом, к нулевому вектору:

Для выражения меры близости в виде числа используется какая-либо норма вектора, например, Евклидова норма или длина вектора в n-мерном пространстве (другое определение – это корень квадратный из скалярного произведения вектора на себя):

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

или норма-сумма (равна сумме абсолютных величин компонентов вектора)

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

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

Приведем такой пример:

Система уравнений

Имеет, как нетрудно убедиться подстановкой, единственное решение x = 1, y = 1.

Предположим, что при подготовке системы к решению, правая часть первого уравнения была определена с небольшой абсолютной погрешностью в +0.01, то есть, правая часть первого из уравнений вместо 11 была взята равной 11,01.

Единственным решение этой системы уравнений уже будет вектор x=11,01 y=0.

Как нетрудно убедится, в этом случае погрешность определения значений переменных оказывается существенно больше, чем погрешность коэффициента. Задачи, в которых малое изменение исходных параметров кардинально сказывается на результате называются плохо обусловленными.

Рассмотрим в общем виде систему линейных уравнений, в которой вектор свободных членов (В) представлен с некоторой абсолютной погрешностью (ΔВ).

Если вектор (X) является точным решением уравнения с "точным" вектором (В).

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

, раскроем скобки в правой части

и учтем точное уравнение

, умножая обе части равенства на матрицу, обратную матрице коэффициентов

получим

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

Если перейти от матриц и векторов к соответствующим нормам, то получим, что норма вектора (ΔX) будет меньше либо равна произведению норм обратной матрицы и нормы вектора погрешности

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

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

Перемножим отдельно левые и правые части неравенств, что, очевидно, не изменит знак неравенства и разделим обе части на и, окончательно получим:

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

Аналогичный анализ можно провести и для случая наличия погрешности задания матрицы коэффициентов системы (ΔA) . И в этом случае, так же, возникает число обусловленности.

Для рассмотренного числового примера

Если взять, например, матричную норму-максимум,

, то получим

для матрицы (А) норму 1011, а для матрицы, обратной (А) - (А)^-1 – 1101. Таким образом, число обусловленности оказывается равным более 1000000!

Прямые (точные) методы

Метод Гаусса и Гаусса-Жордана

Алгоритм решения заключается в приведении расширенной матрицы системы уравнений к треугольному виду (метод Гаусса) или псевдодиагональному виду (метод Гаусса-Жордана).

Метод Крамера

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

, i = 1, 2, …, n

Здесь в знаменателе стоит определитель матрицы коэффициентов системы. В числителе – определитель матрицы, полученной из матрицы коэффициентов путем замены i-го столбца на вектор-столбец свободных членов системы.

Для системы, записанной в общем виде:

и т д.

Метод обращения матрицы

Решение системы уравнений, записанной в матричной форме, легко найти, если воспользоваться определением обратной матрицы:

(A)(A)^-1 = (A)^-1 (A) = (1),

где (1) – единичная диагональная матрица.

Действительно,

Умножим слева обе части уравнения на обратную матрицу коэффициентов системы (A)^-1

Таким образом, для решения системы, необходимо обратить матрицу коэффициентов системы и умножить полученный результат на вектор-столбец свободных членов^.

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

Приближенные (итерационные) методы

Метод простых итераций, метод Зейделя

Данные методы рассмотрены на примере систем нелинейных уравнений.

Метод минимальных невязок

Для решения линейных систем уравнений можно применять и различные методы поиска экстремумов. Проблема решения системы уравнений заменяется эквивалентной задачей нахождения экстремума функции n переменных.

Одним из примеров является метод минимальных невязок. Вектор невязок определяется следующим образом.

Очевидно, что если на место вектора (Х) подставить вектор решения, то второе слагаемое окажется равным вектору свободных членов и вектор невязок становится нулевым.

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

Запишем итерационную формулу поиска решения в следующем виде

где индекс k обозначает номер итерационного шага, тау – константа, которую нам необходимо определить, Δ^(k) (дельта) – вектор невязок на этом шаге.

Рассмотрим разность векторов невязок на двух последовательных шагах k и k+1

после подстановки имеем

Скалярное произведение этого вектора на себя имеет вид

Параметр тау можно выбрать таким образом, чтобы левая часть была минимальной. Условием экстремума является равенство нулю производной по тау правой части выражения

откуда,

Окончательно, k-ый шаг метода выглядит следующим образом:

1. Задается начальное приближение (Х^(k))

2. Рассчитывается вектор невязок

3. Рассчитывается параметр тау. Для этого перемножается матрица коэффициентов и вектор невязок. Затем вычисляется его скалярный квадрат и произведение на матрицу невязок.

4. Рассчитывается новое приближение к вектору-решению

5. Проверяется один из критериев сходимости и, при необходимости, происходит переход к пункту 2.

Задачи, сводящиеся к решению систем линейных уравнений

Примеры решения задач, которые сводятся к нахождению корней системы линейных уравнений можно найти по следующей ссылке:

Свойства смесей веществ

Интеполяция сеточной функций линейными моделями и полиномами

В начало страницы