Современные проблемы прикладной математики (стр. 3 )

; . (3.12)

Для вычисления используем итерационную процедуру ньютоновского типа:

, (3.13)

с начальным значением . В качестве принимается значение , удовлетворяющее (3.12). Заметим, что эта процедура решает нелинейное уравнение , но момент останова определяется условием (3.12).

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

. (3.14)

В формуле (3.14) используется производная , равная , где вектор является решением системы уравнений

. (3.15).

Задание 3.1.

Для построенного регуляризованного решения в лабораторной работе №2 при неполной информации (см. задание 2.3 в работе №2) вычислить:

1) параметр регуляризации ;

2) регуляризованное решение ;

3) ошибку решения

Примечание. При наличии научной задачи магистранта, которую можно свести к системе линейных уравнений, провести исследования этой задачи

§3.2. Алгоритм выбора параметра регуляризации с использованием SVD-разложения на основе критерия оптимальности

Предположим, что:

·  ковариационная матрица допускает представление , и определим сингулярное разложение

, (3.16)

допуская при этом, что сингулярные числа упорядочены по убыванию, т. е. и , где – ранг (или практический ранг) матрицы системы;

·  регуляризированное решение представимо в виде:

, (3.17)

где невозрастающая функция

, где .

Нетрудно показать, что вектор является решением системы

, (3.18)

в которой матрица выражается соотношением:

,

где – матрица размера , составленная из первых столбцов матрицы , входящей в разложение (3.16).

Теперь статистику можно записать в виде

, (3.19)

где векторы , допускают представление:

, (3.20)

(3.21)

где . Тогда

. (3.22)

Введем и функции

, (3.23)

. (3.24)

Для вычисления используем итерационную процедуру:

, (3.25)

с начальным значением . В качестве принимается значение , удовлетворяющее условию

. (3.26)

Задание 3.2.

Для построенного регуляризованного решения в лабораторной работе №2 при неполной информации (см. задание 2.4 в работе №2) используя SVD-разложение, вычислить:

1) параметр регуляризации ;

2) регуляризованное решение ;

3) ошибку решения .

Примечание. При наличии научной задачи магистранта, которую можно свести к системе линейных уравнений, провести исследования этой задачи

§3.3. Алгоритм выбора параметра регуляризации основе статистического принципа невязки

Для вычисления значения проверяется статическая гипотеза

(3.27)

Для проверки (3.27) введем статистику .

Здесь - вектор невязки. Учитывая, что , получим:

(3.28)

Тогда выражение для статистики примет вид:

Введем , получим

.(3.29)

Вычислим производную по . Для этого представим в виде

, (3.30)

где

. (3.31)

Тогда производная от равна

, (3.32)

где

. (3.33)

Вычисление по формуле (3.33) эквивалентно решению системы уравнений

. (3.34)

Для вычисления используем итерационную процедуру ньютоновского типа:

, (3.35)

с начальным условием.

Итерационный процесс завершаем при выполнении условия

. (3.36)

где , – квантили -распределения с степенями свободы уровней , соответственно.

Задание 3.3.

Для построенного регуляризованного решения в лабораторной работе №2 при неполной информации (см. задание 4 в работе №2) вычислить:

1) параметр регуляризации ;

2) регуляризованное решение ;

3) ошибку решения .

§3.4. Алгоритм поиска с использованием SVD разложения

Пусть ковариационная матрица допускает представление . Запишем сингулярное разложение (3.16)

.

Теперь статистику можно записать в виде

, (3.37)

где вектор допускает представление:

(3.38)

Тогда для статистики и ее производной получим

, (3.39)

, (3.40)

где .

Значение , при котором принимается гипотеза (3.27),

удовлетворяет условию

, (3.41)

а , – квантили -распределения с степенями свободы уровней , соответственно.

Для вычисления вновь используем итерационную процедуру ньютоновского типа:

, (3.42)

с начальным значением . В качестве принимается значение , удовлетворяющее (3.41).

Задание 3.4.

Для построенного регуляризованного решения в лабораторной работе №2 при неполной информации (см. задание 2.4 в работе №2) используя SVD-разложение, вычислить:

1) параметр регуляризации ;

2) регуляризованное решение ;

3) ошибку решения .

Примечание. При наличии научной задачи магистранта, которую можно свести к системе линейных уравнений, провести исследования этой задачи

Практическое занятие №4

Локальная регуляризация

§4.1. Векторный параметр регуляризации

Рассмотрим сглаживающий функционал вида

, (4.1)

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

(4.2)

Вместо скалярного параметра регуляризации введем во второе слагаемое этого функционала векторный параметр регуляризации

. (4.3)

Тогда имеем новый сглаживающий функционал:

. (4.4)

Определив матрицу:

, (4.5)

функционал (4.4) можно переписать в виде:

. (4.6)

Введем функционал

(4.7)

и ограничения .

Введем новый сглаживающий функционал (назовем его локальным сглаживающим функционалом)

(4.8)

и определим точку его минимума из условий:

(4.9)

(4.10)

Точку минимума функционала ищем итерационным путем из решения совместных систем вида

, (4.11)

(4.12)

, (4.13)

. (4.14)

Условием прекращения итераций является одновременное выполнение условий:

, (4.15)

где – достаточно малая величина – порядка . В качестве начального значения примем вектор с проекциями

, i=2,..., M, (4.16)

где – оценка по критерию оптимальности (см. п. 3.1).

Значения и в системе (4.12) равны: ,

Задание 4.1.

По формулам (4.11) – (4.16) построить локальное регуляризованное решение, используя найденное в лабораторной работе №3 (см. задание 3.1) глобальное регуляризованное решение.

Практическое занятие №5

Дескриптивные алгоритмы решения СЛАУ

§ 5.1. Глобальный дескриптивный регуляризирующий

алгоритм

Пусть вектор решения принадлежит выпуклому множеству Ф, задаваемому системой линейных неравенств:

, (5.1)

где G – матрица ограничений размером ; g – вектор размерности . Ограничения (5.1) определяют допустимое множество векторов , из которых должен находиться вектор регуляризированного решения. Например, для условия неотрицательности проекций вектора () система неравенств (5.1) преобразуется к виду

, (5.3)

здесь – единичная матрица; – нулевой вектор.

В этом случае искомый вектор , будет являться решением следующей задачи квадратичного программирования :

(5.3)

при ограничениях .

Для приведения исходной задачи к двойственной вновь запишем диагональную матрицу (см. (2.49)):

(5.4)

размером с элементами

, (5.5)

где – ранг матрицы, и введем вектор , составленный из первых проекций вектора .

Тогда регуляризированное решение , доставляющее минимум функционалу (5.3) с матрицей

,

определяется как , где – матрица размером , составленная из первых столбцов матрицы . Вектор

, (5.5)

состоящий из проекций, доставляет минимум функционалу:

(5.6)

Введя обозначения , с учетом и ограничений (5.1), приходим к задаче квадратичного программирования, а именно:

Найти вектор размерности , доставляющий минимум функционалу

(5.7)

при ограничении

. (5.8)

Двойственная по Лагранжу задача формулируется следующим образом:

Задача В. Найти вектор размерности , доставляющий минимум функционалу

(4.1.15)

при ограничении

(5.9)

Решение задачи В можно осуществить используя известные алгоритмы квадратичного программирования.

После вычисления решение задачи А находится из выражения

(5.10)

и состоит из двух слагаемых: регуляризированного решения (5.5), полученного безусловной минимизацией функционала (5.6), и вектора, зависящего от решения двойственной задачи В. Очевидно, что если , то .

Вектор дескриптивного решения находится как

. (5.11)

Таким образом, построение дескриптивного решения можно представить следующими шагами:

·  выполнение сингулярного разложения , где , – сингулярные числа, , – ортогональные матрицы;

·  вычисление вектора из условия минимума функционала (см. (5.5)), т. е.

, (5.12)

где – ранг матрицы системы. При этом вектор осуществляется одним из способов, описанных в лабораторной работе №3;

·  проверка ограничений задачи (5.8). Если ограничения (5.8) выполняются, то ;

·  если ограничения (5.8) не выполняются, то решение вариационной задачи В;

·  формирование вектора , определяемого выражением (5.10);

·  вычисление вектора дескриптивного решения (5.11).

Задание 5.1.

Построить дескриптивный алгоритм решения СЛАУ.

Обратиться к выполненному заданию 3.1. Задать ограничения на искомое решение и найти глобальное регуляризованное решение, удовлетворяющее заданным ограничениям.

§ 5.2. Локальный дескриптивный регуляризирующий

алгоритм

Запишем оптимальное решение (см. (2.18)) для -й итерации

, (5.13)

где диагональная матрица (см. (2.19))

(5.14)

размером имеет элементы

, (5.15)

а вектор составлен из первых проекций вектора .

Величины определяются следующим выражением:

(5.16)

Здесь и определяются как корни квадратного уравнения

, (5.17)

при этом . В формулах (5.19) и (5.20) введены величины:

, (5.18)

где – проекции вектора . В качестве «стартового» решения будем использовать регуляризированное решение , построенное при .

Итерационный процесс прекращаем при одновременном выполнении условий:

, (5.19)

где – достаточно малая величина – порядка .

Введем обозначения: , . С учетом , приходим к следующей задаче квадратичного программирования:

Найти вектор размерности , доставляющий минимум функционалу

(5.20)

при ограничении

. (5.21)

Для данной прямой задачи сформулируем двойственную по Лагранжу задачу

Найти вектор размерности , доставляющий минимум

(5.22)

при ограничении

. (5.23)

Решая данную задачу методами математического программирования, находим вектор и вектор

, (5.24)

где определяется из (5.16). Очевидно, что если , то .

Таким образом, построение дескриптивного локального регуляризированного решения , удовлетворяющего ограничениям , можно представить следующими этапами:

·  вычисляется вектор локального регуляризированного решения (см. (5.13)), удовлетворяющий ограничениям (5.19);

·  проверяются ограничения ;

·  если эти ограничения выполняются, то ;

·  если ограничения нарушаются, то находится решение двойственной задачи (5.22), (5.23) и вычисляется вектор по формуле (5.24);

·  строится вектор решения

. (5.25)

Задание 5.2.

Построить локальный дескриптивный алгоритм решения СЛАУ.

Обратиться к заданию 5.1.

Литература

1. , Мицель проблемы прикладной математики. Часть 1. Лекционный курс: учебное пособие/ Томский гос. ун-т систем управления и радиоэлектроники (ТУСУР). – Томск: 2012. – 136 с.