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

Размещено на http://www.allbest.ru/

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

В.А. Есаулов

Аннотация

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

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

Введение

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

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

Для заданных -матрицы и -вектора линейной задачей о наименьших квадратах называют задачу отыскания такого вектора , который доставляет минимум квадрата евклидовой нормы невязки . Ясно, что для матриц A полного ранга в случае, когда число строк матрицы не превосходит числа столбцов, искомый минимум, как правило, равен нулю [1].

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

(1)

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

, , (2)

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

, (3)

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

, (4)

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

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

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

, (5)

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

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

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

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

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

, (6)

где - частная производная в точке , определяемая как

, , (7)

где .

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

, (8)

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

(9)

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

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

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

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

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

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

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

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

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

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

Таблица № 1.

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

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

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

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

Таблица № 2.

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

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

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

Таблица № 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. Inћenernyj vestnik Dona (Rus), 2012, № 4(part 2) URL: ivdon.ru/ru/magazine/archive/n4p2y2012/1340.

3. Begljarov V.V., Berjoza A.N. Inћenernyj 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.

Размещено на Allbest.ru