- •Глава1. Проблема аппроксимации
- •§1. Полиномиальная апппроксимация
- •§2. Интерполяционный полином в форме Лагранжа
- •§3. Интерполяционный полином в форме Ньютона
- •§4. Аппроксимация сплайнами
- •§5. Метод наименьших квадратов
- •§6. Полиномиальная интерполяция с кратными узлами
- •§7. Свойства разделенных разностей
- •§8. Задача Чебышева. Разрешимость системы
- •§9. Теорема Чебышева
- •§10. Многочлены Чебышева
- •Глава2. Численное дифференцирование
- •Глава3. Численное интегрирование
- •§1. Интерполяционные квадратурные формулы
- •1.Интерполяционные квадратурные формулы
- •2.Интерполяционные квадратурные формулы наилучшей алгебраической точности
- •3.Ортогональные многочлены и их свойства
- •§2. Применение квадратурных формул
- •§3. Метод Монте-Карло (метод статистических испытаний)
- •§4. Правило Рунге практической оценки погрешности
- •Глава4. Алгебраическая проблема собсвенных значений
- •§1. Ортогональные матрицы
- •1.Ортогональные матрицы
- •2.Матрица элементарного поворота
- •§2. Вариационное свойство собственных значений
- •§3. Приведение симметричной матрицы к диагональному виду
- •§4. Сингулярное разложение матрицы
- •§5. Сопряженная матрица
- •§6. Частная спектральная задача
- •1.Вариационный метод
- •2.Степенной метод
- •§7. Метод максимизации столбцов
- •1.Максимизация первого столбца
- •2.Алгоритм сингулярного разложения
- •3.Главное собственное число
- •§8. Метод вращения
§6. Частная спектральная задача
Частная спектральная задача – задача нахождения некоторых собственных чисел матрицы и соответствующих собственных векторов.
1.Вариационный метод
Пусть А – симметричная матрица. Найдем её максимальное собственное число. Т.к. из ранее доказанного , то задача сводится к нахождению стационарных точек функционала.
2.Степенной метод
Для матрицы А предположим, что:
а) её собственные вектора φ1… φnобразуют базис вRn.
б) её собственные числа удовлетворяют неравенствам | λ1 |>| λk|,k=2..n.
Тогда всякий вектор х из Rnможет быть представим в виде:.
Построим последовательность векторов:
x(1)=Ax,x(2)=Ax(1)…x(m)=Ax(m-1)=Amx.
Значит, . Преобразуем правую часть равенства:
приm>>1,
т.к. тогда .
Получим, что:
,
а - соответствующий собственный вектор
(т.к. он определяется с точностью до скалярного множителя).
Знак λ1найдем из следующего равенства:
- знак находится по первой компоненте.
Точность метода: .
§7. Метод максимизации столбцов
Пусть A=(akp) – вещственная, квадратная матрица порядкаn.
Обозначим как ap–pый столбец матрицы.
Заметим, что ; .
Рассмотрим матрицу простого поворота Up:
u11=upp=c=cosα, -up1 =u1p= -s= -sinα, остальные диагональные элементы равны 1, а недиагональные – нулю. Из ранее доказанного матрицаUpосуществляет поворот на угол α против часовой стрелки.
1.Максимизация первого столбца
Рассмотрим матрицу B=AUp=(bij).
В ней: b1=ca1+sap,bp= -sa1+cap. Остальные столбцы совпадают со столбцами А.
Свойство 1
Доказательство
Действительно:
.
Отсюда .
Что и требовалось доказать.
Выберем угол α в матрице Upтак, чтобы |b1| был максимален.
Рассмотрим функцию
Тогда .
Обозначим α=αp:f’(α)=0. Будем выбирать αpпо правилу:
а) если, то
б) иначе αpнаходится из равенства
в)заметим, что αp=0 тогда и только тогда, когда.
Свойство 2 Если |a1|≥|ap|, то |b1|≥|a1|≥|ap|≥|bp| и |b1|>|a1| при.
Доказательство
Действительно:
1)Пусть. Тогдаи.
Следовательно, из определения f(α): .
Отсюда:
и | b1|>|a1| при.
2)Пусть.
Рассмотрим функцию .
Т.к. ,,a, то
f’’(αp)≤0, т.е.αp– локальный максимум () и общий максимум функции на.
Следовательно, .
Что и требовалось доказать.
Свойство 3Если |a1|≥|ap|, то, т.е. новые столбцы ортогональны.
Доказательство
Действительно:
Что и требовалось доказать.
2.Алгоритм сингулярного разложения
Пусть дана матрица A=(aij). Рассмотрим матрицуA1=AU1, гдеU1– ортогональная матрица перестановки столбцов: первый столбец матрицы А1максимален.
Рассмотрим последовательность матриц: Ak+1=AkUp(k),k=1,2…,
где p(k) – номер столбца (= 2,3..n; 2,3..);
Up(k)– матрица простейшего поворота:
u11 = up(k)p(k)= c =cosα, -up(k)1 = u1p(k)= -s = - sinα,
остальные диагональные элементы равны 1,
а недиагональные – нулю.
Т.е. у всех Akпервый столбец максимальный, у всехAk+1первый столбец ортогоналенp(k+1). При этом сумма квадратов сохраняется.
Обозначим . Действительно, тогда.
Отсюда следует лемма:
Лемма 1Последовательность нормпервых столбцов матриц сходится.
Доказательство
По Свойству 2 предыдущего пункта последовательность не убывает.
А из сохранения суммы квадратов она ограничена, а значит сходится.
Замечание Отсюда не следует сходимость векторов.
Лемма 2 Последовательность матриц {Ak} сходится поэлементно приk→∞ (без доказательства).
Т.е. . Эта матрица обладает следующими свойствами:
1)первый столбец наибольший по модулю
2)первый столбец ортогонален всем остальным.
Действительно, предположим противное . Умножим наUp1, получим требуемое.
Таким образом, получен алгоритм сингулярного разложения.
Пусть матрица А nого порядка. Построим последовательностьAk→A∞.
1.Обозначим какв процессе максимализации первого столбца. Т.о. первый столбец макимален и ортогонален всем остальлным.
2.Максимизируем второй столбец матрицы с помощью последующих, не изменяя первый. Полученная последовательность матриц сходится к некоторой матрице.
3.И т.д.
n-1.Максимизируем (n-1)ый столбец у матрицы. Получим матрицус монотонными нормами и взаимоортогональными столбцами.
Запишем полученную матрицу в виде: , где ортогональная матрицаVесть произведение ортогональных матриц.
Обозначим нормы столбцов матрицы какSk.
Получим , гдеW– ортогональная матрица.
Таким образом, AV=WS, т.е.A=WSVT–SVD-разложение.