Документ взят из кэша поисковой машины. Адрес оригинального документа : http://mph.cs.msu.ru/Home/Opus/a78.doc Дата изменения: Tue Apr 6 14:59:48 2010 Дата индексирования: Mon Oct 1 19:43:45 2012 Кодировка: koi8-r

А.Н. Тихонов



О нормальных решениях приближенных систем линейных алгебраических
уравнений


1. Система линейных алгебраических уравнений
[pic], [pic], [pic],[pic],
задаётся с помощью расширенной матрицы [pic]. Если [pic] или при [pic]
детерминант [pic], то условия разрешимости формулируются в виде точных
равенств. Вследствие этого приближенная система [pic] при любой точности
задания [pic] и [pic], как правило, неразрешима. Многие задачи обработки
наблюдений, оптимального проектирования и т.д. приводят к таким классам
систем.
При обработке астрономических наблюдений Лежандром и Гауссом [1,2] был
предложен метод наименьших квадратов (м.н.к.), где в качестве обобщенного
решения системы [pic] предлагается брать элемент [pic], минимизирующий
норму разности [pic]:
[pic] на [pic].
Однако м.н.к. во многих случаях не может являться математической основой
методов для построения алгоритмов автоматизированной обработки наблюдений:
м.н.к. не определяет однозначного решения (если уравнение [pic] имеет
нетривиальные решения); кроме того, он может приводить к неустойчивым
решениям даже при малом возмущении матрицы [pic]. Примером этого является
система
[pic],
[pic].
Введение этой системы в ЭВМ вносит погрешность в её коэффициенты, в силу их
иррациональности, при любой точности. Так, при точности [pic], [pic], [pic]
приближенные системы являются невырожденными и решения их точные, или, что
то же, с помощью метода наименьших квадратов дают
[pic] ; [pic]; [pic] ,
что демонстрирует неустойчивость решений системы с возмущенными
коэффициентами. В этом легко убедиться с помощью элементарных соображений.
Развитию методов получения устойчивых приближенных решений для систем с
возмущенными [pic] и [pic] посвящено значительное число работ (см.,
например, [3-8]).
2. Задание приближенной системы линейных алгебраических уравнений
зависит от доступной информации о ней. Часто такая информация даётся в виде
индивидуальной приближенной системы [pic]. Однако, как было отмечено выше,
этой информации недостаточно.
Мы будем рассматривать приближенные системы, задаваемые с помощью
индивидуальной приближенной системы [pic] и класса систем [pic],
эквивалентных [pic] по точности. Точность задания матриц и векторов будем
оценивать в квадратных нормах. Приближенная система [pic] при этом будет
задаваться как индивидуальная система [pic] и параметры [pic], [pic],
определяющие точность матриц [pic], эквивалентных [pic]:
[pic].
Допустимым решением приближенной системы [pic] будем называть элемент
[pic], если [pic], [pic]. Систему[pic] будем называть совместной, если она
имеет допустимые решения.
Отметим, что система [pic] для любой индивидуальной системы[pic] и
заданного [pic] совместна при достаточно большом[pic].
Обозначим: [pic] - совокупность всех допустимых решений [pic]. По
смыслу постановки задачи все допустимые решения эквивалентны по точности.
Рассмотрим функционал [pic], который будем называть функционалом
сложности. Здесь [pic]- заданный элемент, входящий в постановку задачи. Без
ограничения общности [pic] можно считать равным 0 , что мы и сделаем для
упрощения обозначений.
Нормальным решением приближённой системы [pic] будем называть элемент
[pic], минимизирующий функционал сложности на множестве допустимых решений:
[pic] на [pic].
Задача [pic]. Найти [pic] (нормальное решение [pic]) такой, что
[pic] на [pic],
[pic]
Нетрудно видеть, что справедливы следующие утверждения.
Теорема 2.1. Для всякой совместной системы [pic] существуют нормальное
решение [pic] и система [pic], его реализующая:
[pic], [pic].
Лемма 2.1. Существование допустимого решения [pic] эквивалентно
разрешимости неравенства
[pic], [pic].
Из этой леммы следует, что нахождение нормального решения (решения
задачи [pic]) эквивалентно следующей задаче.
Задача [pic]. Найти такой [pic], что
[pic] на [pic],
[pic]
Величину[pic]будем называть порогом сложности для решений задачи [pic]
(или [pic]), так как не существует допустимых решений [pic] при [pic].
3. Основная лемма 3.1. Пусть даны векторы [pic] и [pic]. Система
уравнений [pic] и относительно [pic] разрешима; решение [pic] этой системы,
минимальное по норме, единственно и даётся формулой
[pic] (или [pic])
и
[pic].
Лемма 3.2. Пусть даны векторы [pic] и [pic]и класс матриц [pic].
Существует единственная матрица [pic], для которой вектор [pic] коллинеарен
[pic]: [pic] при максимальном значении [pic]; эта матрица
[pic], [pic] ; [pic].
4. Убедимся в том, что если [pic] является матрицей, реализующей
нормальное решение [pic], то [pic] и [pic] лежат на границе множеств [pic]
и [pic], т.е.
[pic], [pic].
Лемма 4.1. Если [pic]- какой-либо элемент [pic] и матрица [pic] лежит
внутри [pic] : [pic], то существуют такие [pic]и [pic], что
[pic], [pic], [pic].
Следствие. Если [pic] и [pic], то существуют [pic]и [pic] такие, что
[pic], [pic], [pic].
Отсюда непосредственно вытекает
Теорема 4.1. Если [pic] реализуют [pic]* - нормальное решение системы
[pic], то [pic]
Теорема 4.2. Если [pic] реализуют [pic] - нормальное решение системы
[pic], то [pic].
Таким образом, задача об определении нормального решения задач [pic](или
[pic]) может быть записана как
Задача [pic]. Найти [pic] такой, что
[pic] на [pic],
[pic].
5. Вариационная задача. Найти матрицу [pic], реализующую
[pic] на [pic]
при заданных [pic] и [pic].
Обозначим
[pic]
так что
[pic].
Теорема 5.1. Если [pic], или
[pic],
то разрешимо уравнение [pic].
Следствие. Нормальное решение [pic] (при [pic]) системы [pic] не может
удовлетворять неравенству [pic]. В этом случае [pic] удовлетворяло бы
уравнению [pic] и [pic], но для нормального решения
[pic]
Теорема 5.2. Если [pic], т.е. [pic] то [pic] при условии [pic],
реализуется для единственной матрицы [pic], где
[pic]
Кроме того, имеет место равенство
[pic]
6. Задача [pic]. Найти элемент [pic] такой, что
[pic]
[pic]
Лемма 6.1. Если элемент [pic], то [pic].
Следствие. Всякий [pic]- нормальное решение задачи [pic]- удовлетворяет
условию [pic]т.е.[pic]где [pic]- нормальное решение задачи [pic].
Лемма 6.2. Если [pic]- нормальное решение задачи [pic]и [pic] -
матрица, его реализующая, то матрица [pic], на которой достигается [pic]
совпадает с [pic]: [pic] и
[pic]
т.е. [pic]
Следствие. Всякое нормальное решение [pic] задачи [pic]удовлетворяет
условию [pic]
Теорема 6.1 Множества нормальных решений задач [pic] и [pic] совпадают.
7. Обратимся к доказательству единственности нормального решения системы
[pic] (задача [pic]). Как было доказано выше, все решения задач [pic](или
[pic]), [pic]и [pic] совпадают. Рассмотрим следующие взаимные задачи.
Задача [pic] (взаимная с [pic]). Найти [pic], для которого
[pic] на [pic]
[pic] при [pic]
где [pic]
Задача [pic]. Найти [pic] такой, что
[pic] на [pic],
[pic]
Задача [pic](взаимная с [pic]). Найти [pic] такой, что
[pic] на [pic],
[pic]при [pic]
Решения задач [pic] и [pic]совпадают, так как [pic]и [pic]на
[pic]отличаются фиксированным слагаемым [pic]. Таким образом, решения всех
этих задач [pic](или [pic]) [pic], [pic], [pic], [pic],[pic] совпадают (см.
[9]). Решение задачи [pic], как известно, единственно. Этим доказана
единственность нормального решения системы [pic].
8. Пусть дана система линейных алгебраических уравнений
[pic] [pic]
Будем предполагать, что эта система разрешимая, т.е. что множество решений
этой системы [pic] непусто, и пусть [pic]- нормальное решение системы
[pic].
Пусть система [pic]представляет приближенную информацию относительно
системы [pic] с точностью [pic]:
[pic]
Нормальное решение [pic]системы [pic] дает устойчивое приближение к [pic]
Имеет место следующая
Теорема 8.1. Для любой степени точности [pic] существуют значения [pic]
и [pic] такие, что [pic] - нормальное решение приближенной системы [pic]-
уклоняется от нормального решения [pic]задачи [pic] не более чем на [pic]:
[pic] при [pic], [pic].
Основные результаты этой статьи переносятся на линейные операторные
уравнения [pic] в гильбертовом пространстве, если [pic]- абсолютная норма
[pic], однако последовательность теорем при этом меняется.

Институт прикладной математики им. М.В.Келдыша Академии наук СССР
Поступило 9 VII 1980

Литература

1. А.М. Legendre. Nouvelles mеthodes pour la determination des orbites des
cometes, Paris, Courcier, 1806.
2. C.F. Gauss, Theoria motus corporum coelestium in sectionibus conicis
Solem ambientium, Hamburgi, 1809.
3. А.Н. Тихонов, ДАН, т.163, ?3, 591 (1965).
4. А.Н. Тихонов, Журн. вычислит. матем. и матем. физ., т. 5, ? 4, 718
(1965).
5. А.Н. Тихонов, В.Я. Арсенин, Методы решения некорректных задач, М.,
«Наука», 1979.
6. В.А. Морозов, Журн. вычислит. матем. и матем. физ., т. 8, ? 2, 295
(1968).
7. А.В. Гончарский, А.С.Леонов, А.Г. Ягола, ДАН, т. 203, ? 6, 1238 (1972).
8. В.К. Иванов, В.В. Васин, В.П.Танана, Теория линейных некорректных задач
и ее приложения, М., «Наука», 1978.
9. А.Н. Тихонов, ДАН, т. 253, ? 2 (1980).

* В дальнейшем будем считать, что [pic](это имеет место, если [pic]).