ЛР Численные методы (Трухачев)

Опишем один шаг метода для n-мерного случая. Пусть aij – ключевой элемент матрицы A. Матрица B, подобная матрице A, формируется следующим образом:

1. Вычисляют p=2aij, q= aii-ajj, d = p2 + q2 .

Если q=0, то c = s = 2 .

2

3.Вычисляют новые диагональные элементы:

bii=c2aii+s2ajj+2csaij; bjj=s2aii+c2ajj-2csaij.

4.Полагают bij=bji=0 и для контроля вычисляют

bij=bji=(c2-s2)aij-cs(aii-ajj).

5.При m=1,2,…, n таких, что m≠i и m≠j, вычисляют изменяющиеся внедиагональные элементы:

bim=bmi=cami+samj; bjm=bmj=-sami+camj.

6.Для всех остальных пар индексов m, l принимают bml=aml.

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

Числа, стоящие на главной диагонали данной матрицы, будут собственными числами матрицы A. За собственные векторы xn матрицы A могут быть приближенно приняты столбы

Tk = Ti0 j0 Ti1 j1 ×... ×Tik −1 jk −1 ,

если учесть следующие обозначения:

21

Признаком окончания процесса вращения по методу Якоби может служить малость max bij(k ) .

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

Характеристическим многочленом квадратной матрицы A называется многочлен φ(λ), определяемый равенством

ϕ (λ ) = A − λI = (− 1)n (λn − S1λn−1 + ... + (− 1)n Sn ),

где A − λI – определитель матрицы.

Вычислим характеристический многочлен матрицы B следующего частого вида:

22

Раскрывая определитель (2.6) по элементам первой строки, получим:

Сравнивая выражение (2.7) и определение характеристического многочлена, видим, что коэффициенты pi являются коэффициентами характеристического многочлена матрицы B. Таким образом, учитывая теорему о том, что характеристические многочлены подобных матриц совпадают, если бы некоторую матрицу A подобными преобразованиями удалось свести к виду (2.5), то вычисление характеристического многочлена этой матрицы не представляет труда. Матрицы вида (2.5) носят название матриц в «форме Фробениуса».

Метод Данилевского состоит в приведении матрицы подобными преобразованиями к виду Фробениуса. Заметим, что не все матрицы могут быть приведены к виду Фробениуса, тем не менее характеристический многочлен можно получить для любой матрицы, используя метод Данилевского в достаточно простой модификации.

Пусть A – матрица, характеристический многочлен которой необходимо получить. Если элемент an,n-1≠0, поделим все элементы (n-1)-го столбца на an,n-1. Обозначив a·n-1 – (n-1)-й столбец матрицы

~

A, после деления получим преобразованную матрицу A , у которой

этот столбец на элементы – anj (j=1,2,…,n- 2,n) и складывая с j-м столбцом матрицы A, получим полностью преобразованную матрицу, последняя строка которой имеет вид: (0,0,…,0,1,0). Обозна-

Матрицу Mn-1 можно получить из единичной матрицы, проделав с ее столбцами те же преобразования, что и с матрицей A для полу-

~

чения A . Результатами этих преобразований будет матрица:

23

нию слева на перестановочную матрицу строк. После этого выполнимы все описанные выше преобразования.

столбцу матрицы A в описанных преобразованиях, получим матрицу M n−−12 M n−−11AM n−1M n−2 , подобную исходной с двумя строками в

столбец с любым столбцом j, j<n-2, т.е. со столбцом, расположенным левее (n-2)-го столбца. Для сохранения характеристического многочлена необходимо аналогичное преобразование произвести

~

со строками матрицы A . Заметим, что эти преобразования не изменяют вида уже приведенных строк матрицы. Аналогичным образом преобразуются строки матриц, включая строку с i=2, если описанное выше условие продолжения процесса выполняется, т.е. существует элемент akj≠0, j<k при преобразовании строки с номером k (k≥2). Результатом этих преобразований будет матрица в виде Фробениуса, коэффициенты первой строки которой определяют характеристический многочлен.

Процесс не может быть продолжен, если на некотором шаге окажется akj=0 для всех j<k. К этому моменту преобразованная матрица A имеет вид:

Заметим, что подматрица B2, стоящая в нижнем правом углу размерности (n-k+1)x(n-k+1), имеет вид Фробениуса. Для вычисле-

25

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

ϕ (λ ) = B - λI = B1 - λIk −1 × B2 - λIn−k +1 ,

где B2 – описанная выше матрица вида Фробениуса, а B1 – левая верхняя угловая подматрица B размерности (k-1). Для получения характеристического многочлена необходимо ее преобразовать к виду Фробениуса. Таким образом, применяя метод Данилевского, характеристический многочлен можно получить для любой матрицы A.

Получение собственных векторов по методу Данилевского

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

Ранг матрицы этой системы равен (n-1), поскольку λ – простой корень характеристического уравнения. Это дает нам возможность задать произвольно одну из координат вектора v, например vn=1, и отбросить одно из уравнений системы, являющееся линейно зависимым от остальных. Таким уравнением будет первая строка системы (2.13). Остальные уравнения системы имеют вид:

Зная, что vn=1, из (2.14) при k=n найдем vn−1 = λ .

26

Используя (2.14) при k=(n-1), (n-2),…, 2, последовательно найдем:

Найденный вектор v является собственным вектором матрицы A в базисе, в котором матрица A имеет вид Фробениуса. Пусть T = M n−1 KM1 , тогда

T −1 ATv = λv .

Отсюда

Из (2.16) следует, что (Tv) – собственный вектор матрицы A, соответствующий собственному значению λ и выраженный в базисе, в котором матрица имеет исходный вид A. Таким образом, используя (2.15) и (2.16), установим координаты собственного вектора в исходном базисе.

ПОДГОТОВКА К РАБОТЕ

1.Изучить описание лабораторной работы.

2.Написать программу вычисления всех собственных чисел матрицы с помощью метода вращений Якоби.

Входные параметры программы:

размерность матрицы n;

симметричная вещественная матрица A размерности nxn;

величина ε для оценки малости ключевого элемента. Выходные параметры программы:

вектор собственных значений;

число шагов итерационного процесса.

3.Написать программу определения характеристического многочлена с помощью метода Данилевского.

Входные параметры программы:

размерность матрицы n;

матрица A размерности nxn.

Выходные параметры программы:

матрица в форме Фробениуса.

4.Написать программу получения собственных векторов помощью метода Данилевского.

27

Входные параметры программы:

размерность матрицы n;

матрица A размерности nxn;

вектор собственных чисел. Выходные параметры программы:

набор собственных векторов, соответствующих собственным числам матрицы А.

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1.Отладить программы, реализующие указанные методы.

2.С помощью программы найти все собственные значения указанной матрицы А.

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

ϕ(λ ) = 0 .

4.С помощью программы получения собственных векторов для каждого собственного значения матрицы построить собственный вектор. Проверить выполнение условия Av = λv .

ОТЧЕТ О РАБОТЕ

В отчете о работе должны быть помещены:

1.Название и цель лабораторной работы.

2.Постановка задачи.

3.Исходные данные (размерность матрицы, сама матрица A, величина ε).

4.Получение собственные значения матрицы и количество шагов итерационного процесса.

5.Вид матриц преобразований M (2.9) для каждого этапа преобразований.

6.Вид матрицы в форме Фробениуса и построенный на её основе характеристический многочлен.

7.Результаты проверки всех собственных значений путем их подстановки в построенный характеристический многочлен.

8.Собственные вектора матрицы, соответствующие собствен-

ным значениям, и результаты подстановки их в уравнение Av = λv .

28

КОНТРОЛЬНЫЕ ВОПРОСЫ

1.Приведите определение характеристического многочлена матрицы.

2.Дайте определение собственных значений матрицы.

3.Приведите определение собственного вектора матрицы.

4.Дайте определение подобных матриц. Каким свойством обладают характеристические многочлены подобных матриц?

5.Запишите вид матрицы в форме Фробениуса.

6.Для каких матриц применим метод вращений Якоби? Каково условие останова этого метода?

Величина ε=1·10-4.

СПИСОК РЕКОМЕНДОВАННОЙ ЛИТЕРАТУРЫ

1.Вержбицкий В.М. Основы численных методов. М.: Высшая школа, 2002.

2.Тимохин С.Г. Алгоритмизация вычислений. М.: МИФИ,

1983.

29

Работа 3

ТОЧЕЧНАЯ КВАДРАТИЧНАЯ АППРОКСИМАЦИЯ ФУНКЦИЙ

Ц е л ь : изучение методов точечной квадратичной аппроксимации функций.

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Построение точечной квадратичной аппроксимации некоторой функциональной зависимости y=f(x) может быть актуально в случае, если данная зависимость получена в результате эксперимента, и, следовательно, может содержать ошибки экспериментальных данных.

Чаще всего зависимость между независимой переменной x и зависимой переменной y задается в виде таблицы значений:

Здесь yi≈f(xi) – приближенные значения, получаемые в ходе эксперимента или наблюдений. Требуется подобрать функцию ϕ(x) такую, которая аппроксимировала бы на отрезке [xo ,xn] заданную своими отдельными приближениями yi функцию f(x).

Исходя из некоторых соображений (аналитических, графических или иных) аппроксимирующая функция ϕ(x) берется из определенного m-параметрического семейства функций, и её параметры подбирают так, чтобы сумма квадратов отклонений вычисляемых значений ϕ(xi) от заданных приближенных значений yi была минимальной. Такая функция ϕ(x) будет наилучшей аппроксимаций функции f(x) в смысле метода наименьших квадратов. Очевидно, что для разрешимости задачи число параметров m не должно превышать число приближенных значений yi (как правило, считается,

что n>>m).

Итак, аппроксимирующая функция зависит кроме переменной x от m параметров a1, a2,…, am (m≤n-1): ϕ=ϕ(x,a1,a2,…, am), значения которых определяются из решения экстремальной задачи

30