Итерационный метод решения систем линейных уравнений с использованием q-градиента

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

Итерационный метод решения систем линейных уравнений с использованием q-градиента

В.А. Есаулов

Д.В. Гринченков

В.А. Мохов

Аннотация

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

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

Введение

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

Преимуществом итерационных методов является удобное применение в современной вычислительной технике. Они позволяют получить решение с заранее заданной точностью [3-5].

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

Общая схема организации итерационного процесса решения СЛАУ имеет вид [1, 4]:

, (1)

где , -приближения решения СЛАУ на k-й и (k+1)-й итерациях;

- шаг итерационного процесса.

В ряде итерационных методов решение СЛАУ рассматривают как задачу минимизации функции невязки [4, 5]:

, (2)

где X - вектор переменных целевой функции.

В итерационной постановке (3) может решаться с применением градиентных методов, имеющих вид:

, (3)

, - значения аргумента функции (2) на k-й и (k+1)-й итерациях;

Рассмотрим итерационный процесс решения СЛАУ с применением q-производной [6, 7]. Использование q-производных при расчете антиградиента в методе наискорейшего спуска [6, 8] также дает возможность повышения качества поиска оптимума функции. итерационный уравнение линейный

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

, (4)

Используя в (3) q-градиент с учетом (4) получим следующий итерационный процесс:

, (5)

где , - порядок q-градиента на k-й итерации;

-

главная матрица СЛАУ на k-й итерации.

Из (5) видно, что при фиксированном значении шаг может определяться вариационными методами решения СЛАУ [4, 5]. Так, для метода минимальных невязок, величина рассчитается как

, (6)

Где - величина невязки.

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

, (7)

Рассмотрим варианты расчета оптимальной величины . Общая формула оценки величины может быть сформулирована через оценку минимума (1) на k-ой итерации:

, (8)

С учетом представлений (6), (7), задачу (8) можно переформулировать как задачу поиска следующим образом:

, , (9)

С учетом (5), для формулы (7) оценки задача (8) примет вид

, , (10)

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

При поиске эвристики, адекватно описывающей расчет , будем исходить из определения q-производной (4). Из нее видно, что показывает, во сколько раз отличаются начальная и конечная точки, в которых вычисляются значения функций.

Рассмотрим векторы и . Вектор можно интерпретировать как невязку между приближениями, характеризующую сходимость процесса (1). С учетом связь между координатами и можно представить следующим образом:

(11)

где - матрица перехода, связывающая и ;

- единичная матрица.

Матрицу можно рассматривать как преобразование растяжения , она будет иметь диагональный характер. Коэффициенты растяжения соответственно составят

(12)

где и - i-е координаты векторов и .

Если считать, что компоненты и достаточно близки по своему значению, (23) можно аппроксимировать как

(13)

где - среднее значение.

Выражение (12) можно определить как относительную погрешность координаты относительно . С учетом геометрического смысла (4) элемент можно интерпретировать как порядок частной q-производной функции (2) по переменной . Таким образом, из анализа (12), (13) можно сделать вывод о том, что величину порядка можно оценить по величине погрешности между векторами и .

Если рассмотреть величину порядка q-градиента в смысле (12), (13), то (5) можно записать следующим образом:

(14)

Упростим (14), преобразовав элементы матрицы в одно значение. Для этого оценим параметр порядка q-градиента как погрешность для векторов и следующим образом:

(15)

Формула (15) описывает степень близости и при условии, что на k-й итерации можно рассматривать как точку минимума (1).

От выбора нормы для оценки в (15) зависит точность решения в итерационном процессе (5). Наиболее очевидным решением представляется выбор норм , , как наиболее часто встречающихся в практике оценивания параметров матриц и характеристик итерационных процессов [5].

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

Для сравнительного анализа степени эффективности с методикой (5) и ее вариациями (8)-(15) выбирались методы Зейделя, Якоби, а также минимальной невязки и наискорейшего спуска [9]. Максимальное число итераций для каждого из методов задавалось как 4000. Критерием останова итерационных процессов являлось отношение , где - допустимая погрешность. Величина погрешности задавалась как .

В качестве тестовой СЛАУ выбиралась задача Филипса [10], известная своей плохой обусловленностью. Порядок СЛАУ составил 100. При этом в качестве начального приближения задавался нулевой вектор.

Данные о величине погрешности решения СЛАУ при использовании стандартных методов и (5) с расчетом порядка q-градиента из (9), из (10) приведены в табл. 1.

Таблица № 1.

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

Оценки погрешности решения задачи Филипса при использовании модифицированных методик определения порядка q-градиента приведены в табл. 2.

Таблица № 2

Погрешности решения задачи Филипса при использовании упрощенных методик расчета

Знак "-" в табл. 1, 2 означает, что указанные методы расходятся. Из сравнительного анализа погрешностей в табл. 1, 2 вытекает, что наименьшую величину ошибки для решения задачи Филипса дает методика (5) с использованием (10). Вместе с тем, модификации (13) - (15) оценки порядка градиента дают сопоставимую величину ошибки при более простом способе расчета .

Заключение

В статье предложена методика решения СЛАУ (5) на основе использования q-градиента от функции (2) с возможностью адаптивной оценки его порядка. Вычислительный эксперимент показал ее применимость в отношении решения плохо обусловленных задач. Следующими шагами в модификации методов решения СЛАУ могут стать обобщение проекционных методов решения СЛАУ с учетом использования 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. Хейгеман Л. Прикладные итерационные методы: пер. с англ. / Л. Хейгеман, Д. Янг. - М.: Мир, 1986. - 446 с.

5. Голуб Дж. Матричные вычисления: пер. с англ. / Дж. Голуб, Ч. Ван Лоун. - М.: Мир, 1999. - 548 с.

6. A. C. Soterroni, R. L. Galski and F. M. Ramos, "The q-gradient vector for unconstrained continuous optimization problem" // Operations Research Proceddings 2010, Springer-Verlag Berlin Heidelberg, pp. 365-370 (2011).

7. Ernst, T.: A method for q-calculus. J. Nonlinear Math. Phys. 10, рр.

487-525 (2003).

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

9. Горбаченко В.И. Вычислительная линейная алгебра с примерами на MATLAB. - СПб.: БХВ-Петербург, 2011. - 320 с.

10. Phillips D.L. A technique for the numerical solution of integral equation of the first kind // J.ACM. - 1962. - № 9. - pp. 84-97.

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. Hageman L. Prikladnye iteratsionnye metody [Applied Iterative Methods]: per. s angl. L. Hageman, D. Young. M.: Mir, 1986. 446 p.

5. Golub H. Matrichnye vychisleniya [Matrix Computations]: per. s angl. H. Golub, Ch. Van Loun. M.: Mir, 1999. 548 p.

6. A. C. Soterroni, R. L. Galski and F. M. Ramos, "The q-gradient vector for unconstrained continuous optimization problem". Operations Research Proceddings 2010, Springer-Verlag Berlin Heidelberg, pp. 365-370 (2011).

7. Ernst, T.: A method for q-calculus. J. Nonlinear Math. Phys. 10, рр. 487-525 (2003).

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

9. Gorbachenko V. I. Vychislitel'naya lineynaya algebra s primerami na MATLAB [Numerical Linear Algebra with examples in MATLAB]. SPb: BKhV-Peterburg, 2011. 320 p.

10. Phillips D.L. A technique for the numerical solution of integral equation of the first kind. J.ACM. 1962. № 9. pp. 84-97.

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