Методы решения. Формат выходных данных

Формат выходных данных

Формат выходного файла:

x^*	– решение уравнения;
f(x^*)	– значение функции в найденной точке x^*;
ε^*	– погрешность полученного решения.

2.2. Практическая работа №2 «Решение задач линейной алгебры»

Обязательных методов
Баллов за обязательные методы
Дополнительных методов
Баллов за дополнительные методы
Количество вариантов

К решению задач линейной алгебры в численных методах относят решение систем линейных алгебраических уравнений (СЛАУ) и вычисление различных характеристик матриц – определителей, обратных матриц и собственных чисел и векторов. Для равномерного распределения нагрузки, вычисление собственных чисел и собственных векторов матриц вынесено в отдельную практическую работу (№3).

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

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

Ax = b, (2.2.1)

где A – матрица размером n×m, x – вектор неизвестных длиной m, b – вектор свободных коэффициентов длиной n. Все вектора являются столбцами.

Если n < m, то СЛАУ называется недоопределенной, а если n > m – то переопределенной. Мы будем рассматривать только нормально определенные системы с n = m (т.е. имеющие квадратную матрицу A).

Точность решения СЛАУ можно оценить, вычислив вектор невязки:

ε = Ax^* – b, (2.2.2)

где x^* – приближенное решение СЛАУ.

Для получения скалярной оценки можно использовать норму (1.4).

Учитывая, что точное решение уравнения (2.2.1) для квадратной матрицы можно найти аналитически, т.е.

x^* = A^–1b, (2.2.3)

можно сделать вывод, что единственное решение существует только тогда, когда существует обратная матрица. А для этого, в свою очередь, требуется, чтобы

det A ≠ 0. (2.2.4)

Существуют три класса методов решения СЛАУ [2]:

1. Прямые (точные). Дают решение задачи за конечное число итераций, при этом, если все операции выполняются точно, то и решение получается точным. При реализации на ЭВМ погрешность, конечно же, появляется (по описанным выше причинам – конечность разрядной сетки и т.д.). К прямым методам относятся методы Гаусса, декомпозиции (Халецкого), ортогонализации и др. Прямые методы применяются для решения систем порядка 10³.

2. Итерационные. Дают решение с некоторой точностью как предел последовательных приближений. К итерационным методам относятся методы релаксации, простой итерации, Зейделя, градиентные методы и др. Итерационные методы применяются для систем порядка 10⁷.

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

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

1. Метод Гаусса;

2. Метод декомпозиции;

3. Метод ортогонализации (схема №1).

Дополнительно можно реализовать еще один итерационный метод – Зейделя или простой итерации.

При помощи данных методов необходимо реализовать решение следующих задач:

1. Решение СЛАУ.

2. Поиск определителя матрицы (только для методов Гаусса и декомпозиции).

3. Поиск обратной матрицы.

Дата добавления: 2014-11-20