23. Частичная проблема собственных значений. Нахождение наименьшего собственного значения симметричной матрицы

http://www.bestreferat.ru/referat-95502.html

Определение наименьшего собственного значения методом итераций

В некоторых случаях целесообразно искать наименьшее, а не наибольшее собственное значение. Это можно сделать, предварительно умножив исходную систему на матрицу, обратную A:

А-1АX=lА-1X.

Если обе части этого соотношения умножим на 1/l, то получим

1/lХ = A-1X.

Ясно, что это уже иная задача на собственное значение, для которой оно равно 1/l, а рассматриваемой матрицей является A-1. Максимум 1/l, достигается при наименьшем l. Таким образом, описанная выше итерационная процедура может быть использована для определения наименьшего собственного значения новой системы.

24. Решение систем линейных уравнений методом Гаусса. Обусловленность матрицы

Ме́тод Га́усса[1] — классический метод решения системы линейных алгебраических уравнений (СЛАУ). Это метод последовательного исключения переменных, когда с помощью элементарных преобразований система уравнений приводится к равносильной системе треугольного вида, из которой последовательно, начиная с последних (по номеру), находятся все переменные системы[2].

Описание метода[править | править вики-текст]

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

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

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

При этом будем считать, что базисный минор (ненулевой минор максимального порядка) основной матрицы находится в верхнем левом углу, то есть в него входят только коэффициенты при переменных  [4].

Тогда переменные   называются главными переменными. Все остальные называются свободными.

Если хотя бы одно число  , где  , то рассматриваемая система несовместна, т.е. у неё нет ни одного решения.

Пусть   для любых  .

Перенесём свободные переменные за знаки равенств и поделим каждое из уравнений системы на свой коэффициент при самом левом   ( , где   — номер строки):

, где 

Если свободным переменным системы (2) придавать все возможные значения и решать новую систему относительно главных неизвестных снизу вверх (то есть от нижнего уравнения к верхнему), то мы получим все решения этой СЛАУ. Так как эта система получена путём элементарных преобразований над исходной системой (1), то по теореме об эквивалентности при элементарных преобразованиях системы (1) и (2) эквивалентны, то есть множества их решений совпадают.

Условие совместности[править | править вики-текст]

Упомянутое выше условие   для всех   может быть сформулировано в качестве необходимого и достаточного условия совместности:

Алгоритм[править | править вики-текст]

Блок схема представлена на рисунке. Данный рисунок адаптированный для написания программы на языке С/С++, где a[0] столбец свободных членов.

Алгоритм Гаусса для решения САУ

Описание[править | править вики-текст]

Алгоритм решения СЛАУ методом Гаусса подразделяется на два этапа.

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

• На втором этапе осуществляется так называемый обратный ход, суть которого заключается в том, чтобы выразить все получившиеся базисные переменные через небазисные и построить фундаментальную систему решений, либо, если все переменные являются базисными, то выразить в численном виде единственное решение системы линейных уравнений. Эта процедура начинается с последнего уравнения, из которого выражают соответствующую базисную переменную (а она там всего одна) и подставляют в предыдущие уравнения, и так далее, поднимаясь по «ступенькам» наверх. Каждой строчке соответствует ровно одна базисная переменная, поэтому на каждом шаге, кроме последнего (самого верхнего), ситуация в точности повторяет случай последней строки.

Метод Гаусса требует   арифметических операций.

Простейший случай[править | править вики-текст]

В простейшем случае алгоритм выглядит так:

• Прямой ход:

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

Достоинства метода[править | править вики-текст]

• Для матриц ограниченного размера менее трудоёмкий по сравнению с другими методами.

• Позволяет однозначно установить, совместна система или нет, и если совместна, найти её решение.

• Позволяет найти максимальное число линейно независимых уравнений — ранг матрицы системы[5].

Устойчивость метода Гаусса[править | править вики-текст]

Метод Гаусса для плохо обусловленных матриц коэффициентов является вычислительно неустойчивым. Например, для матриц Гильберта метод приводит к очень большим ошибкам даже при небольшой размерности этих матриц. Уменьшить вычислительную ошибку можно с помощью метода Гаусса с выделением главного элемента, который является условно устойчивым [6]. Широкое применение метода Гаусса связано с тем, что плохо обусловленные матрицы встречаются на практике относительно редко.

Неоптимальность метода Гаусса[править | править вики-текст]

В 1969 году Штрассен доказал, что большие матрицы можно перемножить за время  .[7] Отсюда вытекает, что обращение матриц и решение СЛАУ можно осуществлять алгоритмами асимптотически более быстрыми по порядку, чем метод Гаусса. Таким образом, для больших СЛАУ метод Гаусса не оптимален по скорости.