5Вычислительные задачи линейной алгебры

Вычислительные задачи линейной алгебры подразделяются на:

1.Решение систем линейных алгебраических уравнений (СЛАУ);

2.Нахождение определителей;

3.Нахождение обратных матриц;

4.Задачи на собственные значения.

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

1.Прямые методы для задач линейной алгебры.

2.Итерационные методы решения СЛАУ.

3.Задачи на собственные значения.

5.1Прямые методы для задач линейной алгебры

Ниже будут представлены варианты заданий для прямых методов решения СЛАУ,

а также для их модификаций, позволяющих находить определители

det(A) = |A|

и обратные матрицы A−1

Этапы выполнения:

14

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

n

где n — размерность системы, aij — элементы матрицы A, bi — компо-

ся.

Решение. Написать программу, реализующую заданный численный метод.

Проверка. Задав имя файла, содержащего данные о задаче, запустить программу и получить результат. Программа должна выводить на экран исходные данные10, считанные из файла, решение11, проверку12.

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

11Вектор ~x для задач на решение СЛАУ, матрицу A−1 для задач на обратную матрицу и значение |A| для задач на нахождение определителя.

произведения матриц AA−1. Для задачи на нахождение определителя в качестве проверки будет использоваться результат вычисления определителя по другому методу.

15

Варианты СЛАУ

16

5.2Итерационные методы решения СЛАУ

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

Дополнительное требование: вывести на экран количество итера-

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

1.Метод Якоби

2.Метод Зейделя

3.Метод релаксаций

5.3Алгебраическая проблема собственных значений

Необходимо найти λ и ~x, удовлетворяющие условию:

Тривиальный случай ~x = 0 не представляет практического интереса. Интерес представляют ненулевые собственные значения λ и соответствующие им собственные вектора ~x (в совокупности называемые парой {λ, ~x}). Уравнение A~x = λ~x часто представляют в виде

Вышеприведённое уравнение относится к однородным линейным системам и имеет нетривиальное решение при выполнении равенства

det(A − λE) = 0

17

Задачи на собственные значения подразделяются на частичную (предполагает нахождение одного или нескольких λ из спектра) и полную (нахождение всего спектра собственных значений).

Рассматриваемые здесь численные методы решения задач на собственные значения подразделяются на две категории

1.Методы, направленные на получение коэффициентов характеристического полинома det(A − λE) и на поиск его корней;

2.Методы, использующие преобразования подобия для приведения исходной матрицы A к треугольному или диагональному виду13.

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

Этапы выполнения:

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

Решение. Написать программу, реализующую заданный численный метод.

Проверка. Задав имя файла, содержащего данные о задаче, запустить программу и получить результат. Программа должна выводить на экран исходные данные, считанные из файла, промежуточные результаты15, решение16, номер итерации k, проверку17.

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

14Подробнее см. аналогичный пункт раздела 5.1 «Прямые методы для задач линейной ал-

гебры». Для задач на собственные значения вектор-столбец свободных членов ~ не задаётся; b

если же он присутствует в файле данных, то его следует игнорировать

15Для методов первой категории — график характеристического полинома; для методов второй категории — матрицы преобразований (L, U, Q и т.п.)

16Для методов первой категории — выбранную пару {λ(ik),~xi(k)}; для методов второй кате-

17Для каждой выведенной на экран пары {λ(ik),~xi(k)}, вывести значение величины det(A −

18