Модификация метода наименьших квадратов решения системы линейных уравнений с использованием аппарата квантового анализа

Модификация метода наименьших квадратов решения системы линейных уравнений с использованием аппарата квантового анализа

В.А. Есаулов

Южно-Российский государственный политехнический университет (НПИ) имени М.И.

Платова

Аннотация: Цель и задачи данной работы состоят в развитии методов регуляризации решения систем линейных уравнения (СЛАУ). Для их достижения в работе предложен модифицированный метод наименьших квадратов решения СЛАУ, в основе которого лежит использование q-дифференцирования. Расчеты на примере тестовых задач, выполненные в математическом пакете МайаЬ, подтвердили адекватность метода и в ряде случаев показали его преимущество перед традиционными способами регуляризации СЛАУ.

Ключевые слова: система линейных уравнений, целевая функция, метод наименьших квадратов, предобуславливание, алгоритм, метод регуляризации, q-производная, относительная погрешность, норма вектора, число обусловленности.

Введение

Одним из наиболее эффективных и универсальных методов решения систем линейных уравнений (СЛАУ) является метод наименьших квадратов (МНК). Это связано с тем фактом, что в настоящее время имеется достаточное число высокоэффективных алгоритмов для МНК, а также, что многие статистические свойства оценок решений, полученных на основе МНК для приближенных стохастических СЛАУ при решении задач регрессионного анализа, не зависят от функций распределений возмущений [1]. Рассмотрим суть метода наименьших квадратов и варианты его модификаций.

Построение итерационного метода решения СЛАУ с использованием д-

градиента

Для заданных т х п -матрицы А и т -вектора Ь линейной задачей о наименьших квадратах называют задачу отыскания такого вектора х,

который доставляет минимум квадрата евклидовой нормы невязки ||Лх - Ь||

Ясно, что для матриц Л полного ранга в случае т < п, когда число строк матрицы не превосходит числа столбцов, искомый минимум, как правило, равен нулю [1].

Таким образом, линейная задача на метод наименьших квадратов имеет

вид:

Г \ 2

т / п '

x2,..., хп ) = ||Лх - Ь| 2 =Х I аЦХ3 - Ь ^ т1п

¿=1 V 1= )

Для поиска экстремума (1) составим систему уравнений вида [6]:

д/

дХг

В матричной форме (2) сведется к системе линейных уравнений:

ЛТЛх = ЛТЬ,

Наиболее общий прямой метод решения СЛАУ (3) состоит в применении метода обратной матрицы. В таком случае решение (3) имеет вид

х =

Если матрица ЛТ Л плохо обусловлена, формула (4) перестает давать адекватную оценку решения [2, 3]. Для стабилизации оценок МНК при решении (3) в методе регуляризации по Тихонову в качестве главной матрицы (3) используется матрица вида (лтЛ + х1), где I - единичная матрица, x - параметр регуляризации. Недостатком метода регуляризации является сложность поиска оптимального значения параметра регуляризации. Другой существенный недостаток метода связан с самой идеей регуляризации: сглаживания решения в пределах погрешности измерений. При росте погрешности в качестве решения можно получить более гладкую кривую, все в большей степени отклоняющуюся от истинной [4].

Наряду с постановкой задачи на метод наименьших квадратов и его модификациями представляет интерес исследование методов, использующих неклассическое определение производной. В [5] показано, что обобщение метода Ньютона-Канторовича решения систем нелинейных уравнений, выражающееся в использовании q-градиента, может существенно повысить скорость сходимости процесса поиска решения и повысить его точность. Использование q-градиентных методов показало высокую эффективность для решения задач фильтрации сигналов и параметрической идентификации [6].

Определение q-производной имеет следующий вид [7, 8]:

О/(X) =

/

х * 0

дх - х

й/

йх й/

йх

х=0

д = 1

Геометрическая интерпретация q-производной (1) приведена на рис. 1

[7].

Рис. 1. Геометрическая интерпретация q-производной Из рис. 1 видно, что, в отличие от производной, которая определяет положение касательной в точке, q-производная при значениях д * 1 задает

угол наклона секущей линии. Такое обстоятельство позволяет рассматривать численные методы, использующие q-производную, как некоторую разновидность метода хорд и секущих.

Рассмотрим перспективы использования аппарата q-анализа при решении задачи наименьших квадратов (1). Центральным вопросом будет являться существование q-аналога необходимого условия экстремума (2). На то, что оно может существовать, указывает тот факт, что производная, используемая в (2), является частным случаем производной (5).

Если функция ¥(х) в окрестности точки х0 может быть разложена в формальный степенной ряд, то она может быть аппроксимирована разложением в ряд Тейлора с использованием q-производных [8, 9]:

¥

¿=1

где Б¥(х0) - частная производная в точке х0, определяемая как

Ъ^Р ( х ) =

хг Ф 0

¥ ( х ) - (ея.¥ )( х ) (1 - Ч) хг

ИшБъщ¥

х1 ^ '

д¥ ( х ) 1

, Ч = 1

дх,

где

Если х0 - точка экстремума, то для случая максимума в ней функции ¥ (х) должно выполняться условие ¥(х0) > ¥(х). Рассуждая аналогично [9], получим, что необходимым условием экстремума является равенство нулю ее первых частных q-производных в точке х0, то есть

Бял¥

Записав условие (8) для (1), получим следующее соотношение:

Из вида (9) можно сказать, что в случае плохой обусловленности главной матрицы (3) ATA матрица diag(ATA) может улучшать свойства СЛАУ, увеличивая величину диагональных элементов.

Вычислительный эксперимент

Инструментальным средством реализации изложенных алгоритмов являлась среда. В качестве тестовых задач использовались примеры из библиотеки Regularization Tools для среды MATLAB [10]. Она содержит большой набор различных инструментов решения некорректных задач.

При этом выполнялись следующие действия:

1. Оценка оптимального параметра регуляризации для методов (9), Тихонова и его модификации для МНК;

2. Решение СЛАУ с оптимальными параметрами регуляризации для каждого из методов;

3. Вычисление погрешности, описывающей отклонения полученного решения от известного точного.

Параметр регуляризации задавался в диапазоне значений от 0 до 0.01. Оптимальным считался параметр регуляризации, при котором решение СЛАУ доставляет функции (1) минимум из всего диапазона значений. Погрешность решения СЛАУ определялась как относительная погрешность приближенного решения по отношению к тестовому в смысле нормы Щ 2.

В качестве первой тестовой задачи бралась СЛАУ, описывающая задачу Fox&Goodwin [11]. Порядок главной матрицы задавался равным 100, а ее число обусловленности составило cond (A) = 2.26 • 1018.

В табл. 1 приведены значения относительных погрешностей решений для задачи Fox&Goodwin.

Таблица № 1.

Сводная таблица погрешностей решения задачи Fox&Goodwin

Метод решения СЛАУ Погрешность, %

Формула (9) 5.3

Метод Тихонова с МНК 0.49

Метод Тихонова 34.2

По данным табл. 1 можно видеть, что метод Тихонова для МНК дает наименьшую погрешность. Решение по методике (9) дает удовлетворительное совпадение с точным решением, гораздо большее по точности по сравнению со случаем использования традиционного метода Тихонова.

В качестве второй тестовой задачи выступила СЛАУ с двухдиагональной матрицей из примера Годунова [12]. Этот пример интересен тем, что является достаточно сложной задачей для метода Тихонова и его вариаций [4]. Порядок главной матрицы из примера Годунова задавался равным 100. Число обусловленности главной матрицы составило евМ(Л) -1.05 -1042.

В табл. 2 приведены значения оптимального параметра регуляризации для разных методов расчета

Таблица № 2.

Значения параметра регуляризации для примера Годунова

Методика Значения параметра Значение функции

регуляризации регуляризации

Формула (9) 1.9073e-06 1.0185e-06

Метод Тихонова с 1.9083e-06 1.7229e-07

МНК

Метод Тихонова 1.490^-08 4.7303e+23

Из данных в табл. 2 можно сделать вывод, что метод Тихонова с найденным значением оптимального параметра регуляризации не может обеспечить адекватного решения данной задачи. Ввиду этого при решении СЛАУ метод Тихонова не применялся.

В табл. 3 приведены значения относительных погрешностей решений для примера Годунова.

Таблица № 3

Значения погрешностей решений примера Годунова

Методика регуляризации Погрешность, %

Формула (9) 13.48

Метод Тихонова с МНК 52.3

Из табл. 4 видно, что, решение СЛАУ [12] по методике (9), обеспечивает наименьшую погрешность в сравнении решением, полученным при использовании метода Тихонова с МНК.

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

Заключение

В статье предложена (9) решения СЛАУ на основе использования q-градиента в необходимом условии экстремума для (1). Вычислительный эксперимент показал ее применимость в отношении решения плохо обусловленных задач. Следующими шагами в развитии предложенной методики могут стать получение итерационных методов на основе (9), а также разработка способов адаптивного определения порядка q- градиента для них.

Литература

1. Шарый С.П. Курс вычислительных методов. Учеб. пособие. -Новосибирск: Новосиб. гос. ун-т. , 2014 г. , 279 с.

2. Целигоров Н.А., Целигорова Е.Н., Мафура Г.В. Математические модели неопределённостей систем управления и методы, используемые для их исследования. Инженерный вестник Дона, 2012, № 4(часть 2) URL: ivdon.ru/ru/magazine/archive/ n4p2y2012/1340.

3. Бегляров В.В., Берёза А.Н. Гибридный эволюционный алгоритм решения систем линейных алгебраических уравнений, описывающих электрические цепи. Инженерный вестник Дона, 2013, №1 URL: ivdon.ru/ru/magazine/archive/ n1y2013/1540.

4. В.В. Дикусар. Некоторые численные методы решения линейных алгебраических уравнений // Соросовский образовательный журнал, № 9, с. 111-120.

5. Predrag M. Rajkovic', Sladjana D. Marinkovic', Miomir S. Stankovic'. On q-Newton-Kantorovich method for solving systems of equations. // Applied Mathematics and Computation 168 (2005), pp. 1432-1448

6. Ubaid M. Al-Saggaf, Muhammad Moinuddin, Muhammad Arif, Azzedine Zerguine. Theq-Least Mean Squares algorithm // Signal Processing 111 (2015), pp. 50-60.

7. Soterroni, Aline Cristina. O m'etodo do q-gradiente para otimiza,c~ao global // Aline Cristina Soterroni - S~ao Jos'e dos Campos: INPE, 2012. - 151 p.

8. В.Г.Кац, П.Чен. Квантовый анализ / Перевод с англ. Ф.Ю.Попеленского и Ж.Г.Тотровой. М.: МЦНМО, 2005. 128 с.

9. Гаврилов, В.И. Математический анализ: Учебное пособие для студентов учреждений высшего профессионального образования / В.И. Гаврилов, Ю.Н. Макаров, В.Г. Чирский. - М.: ИЦ Академия, 2013. - 336 c

10. P. C. Hansen. Regularization of discrete ill-posed problem // Numerical Algorithms 46 (2007), pp. 189-194.

11. C. T. H. Baker. The Numerical Treatment of Integral Equations, Clarendon Press, Oxford, 1977; p. 665.

12. Годунов С.К. Решение систем линейных уравнений. - Новосибирск: Наука, 1980. - 178 с.

References

1. Sharyj S.P. Kurs vychislitel'nyh metodov. Ucheb. Posobie [The course of computing methods. Tutorial.]. Novosibirsk: Novosib. gos. un-t., 2014 g., 279 p.

2. Celigorov N.A., Celigorova E.N., Mafura G.V. Inzenernyj vestnik Dona (Rus), 2012, № 4(part 2) URL: ivdon.ru/ru/magazine/archive/n4p2y2012/1340.

3. Begljarov V.V., Berjoza A.N. Inzenernyj vestnik Dona (Rus), 2013, №1 URL: ivdon.ru/ru/magazine/archive/ n1y2013/1540.

4. V.V. Dikusar. Sorosovskij obrazovatel'nyj zhurnal, № 9, pp. 111-120.

5. Predrag M. Rajkovic', Sladjana D. Marinkovic', Miomir S. Stankovic'. On q-Newton-Kantorovich method for solving systems of equations. Applied Mathematics and Computation 168 (2005), pp. 1432-1448.

6. Ubaid M. Al-Saggaf, Muhammad Moinuddin, Muhammad Arif, Azzedine Zerguine. Theq-Least Mean Squares algorithm. Signal Processing 111 (2015), pp. 50-60.

7. Soterroni, Aline Cristina. O m'etodo do q-gradiente para otimiza,c~ao global Aline Cristina Soterroni - S~ao Jos'e dos Campos: INPE, 2012. 151 p.

8. V.G.Kats, P.Chen. Kvantovyy analiz [Quantum analysis]. Perevod s angl. F.Yu.Popelenskogo i Zh.G.Totrovoy. M.: MTsNMO, 2005. 128 p.

9. Gavrilov, V.I. Matematicheskij analiz: Uchebnoe posobie dlja studentov uchrezhdenij vysshego professional'nogo obrazovanija [Mathematical analysis:

Textbook for students of institutions of higher education]. V.I. Gavrilov, Ju.N. Makarov, V.G. Chirskij. M.: IC Akademija, 2013. 336 p.

10. P. C. Hansen. Regularization of discrete ill-posed problem. Numerical Algorithms 46 (2007), pp. 189-194.

11. C. T. H. Baker. The Numerical Treatment of Integral Equations, Clarendon Press, Oxford, 1977; p. 665.

12. Godunov S.K. Reshenie sistem linejnyh uravnenij [Solving systems of linear equations]. Novosibirsk: Nauka, 1980. 178 p.