Н.Н. Калиткин - Численные методы (1133437), страница 42

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 42)

к наименьшему по модулю собственному значению матрицы А (ибо собственные значения матриц А и А' обратны друг другу). Все, что говорилось в предыдущем пункте о характере сходимости, разумеется, справедливо и в этом случае; сходимость будет довольно медленной. Однако здесь положение можно суц~ественно улучшить лгвто. дом сдвига, который заключается в следующем.

Пусть нам приближенно известно некоторое, не обязательно наименьшее, собственное значение Ль Тогда так называемая сдвинутая матрица (А — Л,Е) будет иметь собственные значения Л вЂ” Ло У этой матрицы интересующее нас собственное значение Л; — Л, будет намного меньше по модулю, чем остальные. Поэтому обратные итерации со сдвинутой матрицей (которые мы запишем в несколько иной форме) (А — ЛЕ) хь "м =х('>. (74а) >92 АЛГЕБРАИЧЕСКАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИЙ (ГЛ. Ч! будут быстро сходиться и определят требуемое нам собственное значение Ц вЂ” )(. Напомним, что после каждой итерации надо нормировать вектор, чтобы избежать переполнений. С учетом этого вместо (74а) получим последовательность формул (А — ЦЕ)у(5) = Х(5>, (х(5)' у~5~ (74б) ((9(5>(5 (~~~Я ) Здесь индекс й относится к компонентам векторов, а скобки (...) означают некоторое усреднение по всем компонентам: например, среднеарифметическое.

Если исходное приближение было хорошим, то иногда процесс сходится за несколько итераций; тогда выгодно непосредственно решать линейную систему (73). Если же требуемое число итераций велико, то лучше обратить матрицу (А — Х(Е). Выгодней всего при решении линейной системы (74) методом исключения Гаусса использовать полученные на первой же итерации вспомогательные коэффициенты с „(см. главу т>, 9 1, п.

1) на каждой последующей итерации; но это не предусмотрено в обычных стандартных программах. Если сдвиг постоянный, то итерации сходятся линейно, Можно получить квадратичную сходимость, если уточнять сдвиг в ходе расчета следующим образом: (А — Л~'Е) у(5> = Х(5', (,> /Х~5>'1 Ч'5' (75) )) у|5) /! Для матриц, имеющих ортогональную систему собственных векторов (например, эрмитовых матриц), сходнмость вблизи корня будет даже кубической.

Заметим, что допускать слишком точное совпадение Ц с собственным значением нельзя, ибо мвтрица системы (75) становится плохо обусловленной; Об этом уже говорилось в 9 1, п. 6 в связи с нахождением собственных векторов. Поэтому, когда в ходе итераций у величины )(' устанавливаются (т. е. перестают меняться) 5 — ? знаков, то итерации следует прекращать. Замечание 1. Переменный сдвиг собственного значения (75) нельзя включать с первой итерации; сначала надо получить грубую сходимость итераций с постоянным сдвигом. Замечание 2.

Обратные итерации особенно удобны, если матрица заранее приведена преобразованием подобия к почти треугольной форме. Тогда одна обратная итерация выполняется 133 ЗАДАЧИ методом исключения с выбором главного элемента всего за 2из действий. Теоретически для ленточных матриц возможна еще ббльшая экономия, но преобразование подобия почти треугольной матрицы к трехдиагональной форме не всегда устойчиво. Выводы.

Обратные итерации с постоянным и особенно с переменным сдвигом — очень эффективный метод расчета. Для нахождения собственных векторов этот метод считается наиболее точным. Сходимость при хорошем подборе )ь настолько быстрая, что метод пригоден и для близких нли случайно равных по модулю собственных значений (ибо после сдвига они хорошо различаются), и даже при наличии у матрицы нелинейного элементарного делителя. ЗАДАЧИ 1.

Доказать, что если матрица и-го порядка имеет и собственных векторов ег=- (61ч), 1 =- и = л, то она диагональна. 2. Найти собственные векторы треугольной матрицы, считая все собственныс значения простыми. 3. Доказать, что нормальная матрица при унитарном преобразовании подобия остается нормальной. 4. Показать, что если матрица А ленточная, то преобразование подобия матрицами отражения (30) не сохраняет ее структуры, 5.

Какие элементы необходимо вычислять в формулах (43) — (44) при преобразовании подобия матрицами вращения для зрмитовой матрицы А? 6. Доказать, что сферическая норма произвольной матрицы не меняется при умножении с любой стороны на унитарную матрицу. 7. В итерационном методе вращений вывести для определения параметров поворота комплексных матриц формулу, аналогичную (51). 3. Показать, что в нтерациовном методе вращений формулы (54) определяют собственные векторы с точностью О (ез), где е — максимум модулей внедиагональных элементов; если же в этих формулах положить у;ь Нь то точность ухудшается до 0(е). 9. Получить все формулы расчета матричных элементов для второго хода метода элементарных преобразований. 16.

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

12, а) Какой вид примут формулы метода линеаризапии (70), если недостающее уравнение получать из условия нормировки собственного вектора п ~~ (хг',з=1? 5) Как построить экономичный алгоритм решения полученной г=1 при этом линейной системы, если матрица А является трехдиагональной? 13. Доказать, что метод обратных итераций с переменным сдвигом (75) сходится квадратичво вблизи простого собственного значения.

ГЛАВА 7!1 ПОИСК МИНИМУМА В главе 711 рассмотрены способы нахождения такого значения аргумента, которое минимизирует некоторую зависящую от него скзлярную величину. В $1 изложена задача о минимуме функции одного переменного, лежащая в основе всех более сложных задач, В 5 2 рассмотрена задача о минимуме функции многих переменных в неограниченной области. В 4 3 область изменения переменных ограничена; наряду с общим случаем рассмотрена частная задача линейного программирования, важная в приложениях к кономике. В $ 4 разобрана задача о минимизации функционала, когда аргумент сам является функцией одного илн нескольких переменных.

В 1. Минимум функции одного переменного 1. Постановка задачи. Пусть имеется некоторое множество Х, состоящее из элементов х, принадлежащих какому-нибудь метрическому пространству, и на нем определена скалярная функция Ф(х). Говорят, что Ф(х) имеет локальный минимум на элеменаге х, если существует некоторая конечная е-окрестность этого элемента, в которой выполняется Ф (х) Ф (х), )) х — х () ~ е. (1) У функции может быть много локальных минимумов.

Если же выполняется Ф (х) = !п( Ф (х), (2) х то говорят о достижении функцией абсолюгпного минимума на данном множеспюе Х. Естественно требовать„чтобы функция Ф (х) была непрерывной или, по крайней мере, кусочно-непрерывной, а множество Х было компактно') и замкнуто *а) (в частности, если Х само является ') Множество компактно, если из каждого бесконечного и ограниченного его подмножества можно выделить сходящуюся последовательность. "') Множество замкнуто, если предел любой сходящейся последовательности его злементов принадлежит атому множеству. э» минимгм ьэнкции одного паявменного пространством, то это пространство должно быть баяаховым).

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

Перечислим наиболее важные примеры множеств, на которых приходится решать задачу нахождения минимума. Если множество Х является числовой осью, то (1) илн (2) есть задача на минимум функции одного вещественного переменного. Если Х есть и-мерное векторное пространство, то мы имеем дело с задачей на мияимум функции и переменных. Если Х есть пространство функций х(1), то (1) называют задачей на минимум функционала. Для нахождения абсолютного минимума есть только один способ: найти все локальные минимумы, сравнить их и выбрать наименьшее значение. Поэтому задача (2) сводится к задаче (1), и мы будем в основном заниматься задачей поиска локальных минимумов.

Известно, что решение задачи (1) удовлетворяет уравнению — = О. 6Ф (3) Если множество Х есть числовая ось, то написанная здесь производная является обычной производной, и тогда уравнение (3) есть просто одно (нелинейное) уравнение с одним неизвестным. Для п-мерного векторного пространства соотношение (3) оказывается системой нелинейных уравнений дФ(дх; = О, 1 ~1 = л. Для пространства функций уравнение (3) является дифференциальным или интегро-дифференциальным.

В принципе такие уравнения можно решать численными методами, описанными в главах Ч и Х1Ч, Однако эти уравнения нередко имеют сложный вид, так что итерационные методы их решения могут очень плохо сходиться или вообще не сходиться. Поэтому в данной главе мы рассмотрим численные методы, применимые непосредственно к задаче (1), без приведения ее к форме (3). Пусть Х является некоторым множеством, принадлежащим какому-то пространству. Тогда (1) называют задачей на минимум в ограниченной области. В частности, если множество Х выделено из пространства с помощью ограничивающих условий типа равенств, то задачу (1) называют задачей на условный экстремум; такне задачи методом неопределенных множителей Лагранжа часто можно свести к задачам на безусловный экстремум.

Характеристики

Список файлов книги