18. Компьютерный алгоритм. Точность компьютерных алгоритмов

Компьютерный алгоритм можно рассматривать как другое отображение ~ : → между этими двумя пространствами. Пусть даны фиксированные: задача , компьютер (система вычислений с плавающей точкой которого удовлетворяет (17.2)) (но не обязательно (17.1)), алгоритм для решенияи реализация этого алгоритма в форме компьютерной программы. Пусть исходные данные переведены в систему с плавающей точкой таким образом, что выполняется аксиома 16.1, и переданы на вход компьютерной программе. Результат — ~( ) .

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

‖~( ) − ( )‖ или относительную ошибку

Если ~ – "хороший" алгоритм, действительно можно ожидать, что относительная ошибка будет малой, т.е. порядка машинного эпсилон machine. Можно сказать, что алгоритм ~ для задачи точен, если для каждого выполняется

19. Устойчивость и обратная устойчивость компьютерных алгоритмов

Компьютерный алгоритм ~ для задачи называется устойчивым, если для каждого

Другими словами, устойчивый алгоритм дает ответ, близкий к верному, для задач c входными данными близкими к точным.

Компьютерный алгоритм ~ для задачи называется обратно устойчивым, если для каждого

выполняется:

~( ) = (~) для некоторых ~ таких, что

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

20. Приближённые некорректные СЛАУ

Рассмотрим некоторую задачу

= ,

где R × , R . Некорректной принято называть задачу, в которой решение возмущений не стремится к псевдорешению при → 0, то есть:

lim |^ − ^( )| = ∞.

→0

Корректная задача обладает свойствами: существования, единственности и устойчивости (малое возмущение должно соответствовать малой погрешности). Если хотя бы одно из условий не выполняется, задача так же называется некорректной.

10

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

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

21. Метод регуляризации А. Н. Тихонова

Одним из наиболее универсальных методов является метод регуляризации А.Н. Тихонова. Этот метод определяется:

= ( ), > 0,

R

где — сглаживающий функционал Тихонова, определяющийся следующим образом:

( ) = ( , , ) = ‖ − ‖2 + ( ),

где , — априорная информация, а ( ) = ‖ − 0‖2 — стабилизирующий функционал. Вектор 0 является априорно заданным пробным решением. В случае, если 0 = , очевидно, ( ) = ‖ ‖2.

Минимизация сглаживающего функционала Тихонова , очевидно, приводит к уравнению:

( T + ) = + 0,

называемому регуляризируемой нормальной системой или уравнением Эйлера. Чтобы сходилась к точному решению * необходимо, чтобы:

lim ‖ − *‖ = 0,

→0

в таком случае будет регуляризующим оператором.

22. SVD-разложение и решение линейных систем

Решение системы

где = * = ( , ), называемые коэффициентами разложения вектора правой части по сингулярным векторам 1, 2, . . . , .

Данное утверждение проясняет роль направления возмущений при решении систем. Если коэффициент заменяется на + , где — некоторое возмущение, то коэффициент при векторе в разложении вектора * по базису 1, 2, . . . , возмущается на величину / . Таким образом, чем меньше , тем сильнее может измениться решение. Возмущение решения определяется не только

‖ ‖

отсительной погрешностью в векторе , то есть ‖ ‖ , но и направлением возмущений.

23. Метод наименьших квадратов и SVD-разложение

Рассмотрим уравнение

= ,

где C × , > . Рассмотрим задачу наименьших квадратов, то есть нахождения

нормальное псевдорешение имеет вид

* = + .

11

Пусть C × , = . Тогда множество псевдорешений является линейным многообразием с размерностью − .

Из всех псевдорешений выделяется единственное, которое является нормальным псевдорешением. Нормальное псевдорешение существует всегда.

SVD-разложение позволяет дать явный вид нормальному псевдорешению:

∑

*

^ = · .

=1

Однако, несмотря на простоту формулы, могут возникнуть проблемы. Основная проблема возникает в случае, если матрица — неполного ранга, то есть < min( , ). Причиной этому является то, что ранг может повыситься при сколь угодно малом возмущении.

24. Псевдообратная матрица и SVD-разложение

Для любой матрицы C × существует сингулярное разложение (SVD-разложение) вида

= *.

Тогда из утверждения о том, что для любой матрицы C × выполнено соотношение

‖ + − ‖ 6 ‖ − ‖ .

непосредственно следует, что псевдообратная матрица

метод является самым надежным (по точности) способом определения псевдообратных матриц, но в тоже время он является самым трудоемким (с вычислительной точки зрения) методом.

25. Наилучшие аппроксимации матриц с понижением ранга

Под аппроксимацией матрицы понимается замена исходной матрицы на матрицу, состоящую из суммы меньшего числа слагаемых с разделёнными переменными и .

Теорема 25.1. Пусть матрица C × задана сингулярным разложением вида

и условимся считать, что +1 = 0. Пусть задано целое 1 6 6 . Тогда

min ‖ − ‖2 = +1 = ‖ − ‖2,

6

C ×

26. Расстояние до множества вырожденных матриц

Если — невырожденная матрица, то все матрицы + при достаточно малой норме ‖ ‖2 будут невырожденными. Под спектральным расстоянием между и множеством вырожденных матриц понимается величина

Из теоремы об аппроксимациях с понижением ранга 25.1 вытекает, что

Таким образом, спектральное расстояние от заданной невырожденной матрицы до множества вырожденных матриц равно её минимальному сингулярному числу.

12

27. SVD и регуляризация

Использование сингулярного разложения даёт простой способ вычисления регулярных решений

Решение задачи наименьших квадратов с использованием SVD имеет вид:

∑

T

= =1

Так как T = T , регуляризируемая нормальная система будет иметь вид

( T + ) = T .

тогда

Уравнение 27.2 даёт возможность легко вычислить регулярные решения с любым параметром регуляризации. Сингулярное разложение показывает, что регуляризационный алгоритм Тихонова является алгоритмом фильтрации.

13