Статья по теме:
Точное решение СЛАУ методом простых итераций
Исхаков Альберт Саитович, доктор технических наук АО «Корпорация «ВНИИЭМ» директор по инновационному развитию специальных программ г. Москва, Россия
Сковпень Сергей Михайлович, кандидат технических наук, доцент, Северный (Арктический) федеральный университет им. М.В. Ломоносова, Филиал в г. Северодвинске, Институт судостроения и морской арктической техники, кафедра автоматики и управления в технических системах г. Северодвинск, Россия
Аннотация
В статье авторами впервые приводится теорема с доказательством решения системы линейных алгебраических уравнений (СЛАУ) за конечное число итераций со стационарной матрицей. Преобразование системы должно быть направлено на получение матрицы со спектром в единице. Расщепление ее дает нильпотентную матрицу итерационной системы, генерирующей точное решение СЛАУ за число итераций, не превышающее размерности.
Ключевые слова: нильпотентная и унипотентная матрицы, метод простых итераций, конечный итерационный процесс со стационарной матрицей
Большая часть математического сообщество считает недостижимым получение точного решения этим методом за конечное число итераций. В частности, такого взгляда в своих работах придерживаются следующие Российские и иностранные ученые: Фаддеев Д.К., Фаддеева В.Н., Strang G., Самарский А.А., Николаев Е.С., Demmel W.D. [1-4]. Однако это мнение противоречит теории управления, где для линейной дискретной системы, характеризуемой таким же уравнением, известен метод достижения заданного положения за конечное число шагов. Данное же направление активно разрабатывали такие ученые, как Квакернаак Х., Сиван Р., Изерман Р., Первозванский А.А. [5-7].
Парадоксальность состоит в том, что в теории управления для линейной дискретной системы, описываемой системой формально таких же итерационных уравнений, достигается заданное положение за конечное число шагов. Здесь принципиальным моментом является преобразование уравнения к виду с нильпотентной матрицей с помощью матрицы Фробениуса. В итоге этот метод, вообще говоря, можно перенести на СЛАУ, но с ограничением - для однородного случая.
Другой способ получения нильпотентной матрицы итерационного уравнения снимает это ограничение. Выполнение обратного перехода от итерационной системы с нильпотентной матрицей к СЛАУ приводит к унипотентной матрице. Это означает, что условием решения СЛАУ за конечное число итераций является преобразование ее матрицы к виду с расположением спектра в единице. Примером может служить метод Гаусса, где матрица, приводимая к треугольной форме с единичной диагональю, расщепляется на единичную и строго треугольную, являющуюся нильпотентной. В этой связи решение (обратный ход) формально может считаться итерационным процессом с не плотной матрицей, не требующим операции умножения матрицы на вектор, что и выполняется на практике. Нам же удалось получить конечный итерационный процесс с плотной нильпотентной матрицей.
В тексте статьи ниже, впервые авторами приводится соответствующая теорема и ее доказательство, которое оказалось удивительно коротким. Основой метода является преобразование, позволяющее получить нужный спектр матриц - единичный для алгебраической системы и нулевой для итерационной. Отдельные положения изложены в ранее опубликованных авторами научных трудах [8-10], в частности в «Exact Solution of a Linear Difference Equation in a Finite Number of Steps» [10] приведены итерационные уравнения для СЛАУ второго порядка, заданной в аналитической форме.
Авторы теории и теоремы просят задержать внимание на истории вопроса. Первый результат был получен еще в 2001 году при разработке варианта апериодического алгоритма управления, целью которого было устранение преобразования матрицы к форме Фробениуса, необходимое в известном методе и требующее временных или аппаратных затрат. Это удалось за счет другой обратной связи - вместо вектора состояния была использована его первая разность. В такой форме уравнение движения линейной дискретной системы стало формально представлять частный случай канонической формы двухслойного итерационного метода. Для уравнения было разработано оригинальное преобразование на основе зависимостей между элементами матрицы и ее спектром - формул Виетта, что позволило вычислить элементы вектора обратной связи для задания желаемого спектра матрицы.
Так была решена инженерная задача, в последствии авторами выяснилось, что совокупность использованных приемов дала новый качественный эффект и для математики - метод решения СЛАУ со свойствами прямых и итерационных методов.
Наши коллеги вначале воспринимали метод с недоверием, что естественно, так как он опровергает устоявшееся мнение. Интригу, если уместно здесь употребить этот термин, усиливает факт отсутствия у авторов классического университетского математического образования. Хотя они имеют большой опыт разработки электротехнических систем, в частности полупроводниковых преобразователей электроэнергии, и опубликовали по этой тематике значительное число работ.
Большой период времени у авторов ушел на самообразование в области вычислительной математики и на овладение навыками изложения математических работ. В качестве теоретической основы метода в трех журналах опубликован способ задания спектра матриц, не связанных уравнениями, отличный от тривиального, с точки зрения линейной алгебры, варианта с преобразованием к форме Фробениуса. В прошлом году (2019 г.) работа по точному решению линейного разностного уравнения за конечное число шагов, фактически опровергающая мнение о приближенности метода простых итераций, опубликована в четырех журналах.
Авторы готовы предоставить более детальное и в то же время популярное изложение варианта метода с названием «О конечных стационарных итерационных процессах» в виде трех отдельных частей:
I. Конечный итерационный процесс в системе с численными коэффициентами
II. Матрицы алгебраической и итерационной систем для конечных процессов
III. Преобразование СЛАУ к итерационной форме с нильпотентной матрицей
Теорема. Для решения СЛАУ
линейный алгебраический уравнение итерация
Ах = b, (1)
где х и b - соответственно, неизвестный и известный векторы размерности k,
А - квадратная невырожденная матрица размера k., за конечное число итераций, необходимо и достаточно привести к виду
Ех = с, (2)
с унипотентной матрицей со спектром из единиц. Тогда итерационное уравнение
хn+1 = Nхn + c (3)
где n = 0, 1, 2, …, Е = I - N, генерирует точное решение без учета погрешностей округления
х = А -1b = Е -1с (4)
при произвольном начальном векторе х0 не более, чем за m ? k итераций,
Доказательство. Матрица Е расщепляется на единичную I и нильпотентную матрицу N, со свойством
Nk = 0 (5)
Не унипотентная матрица не образует нильпотентную и решение (3) при с = 0
хn = Nnх0 (6)
будет зависеть от х0, что доказывает необходимость
Достаточность следует из решения (3) с учетом (5) при n = k
хk = Nkх0 + (I + N + … + Nk-1)с = (I - N) -1с = х (7)
Замечания.
1. Метод простых итераций считается приближенным из-за распространения условия detA ? 0 на матрицу итерационного уравнения, но как следует из теории управления и здесь подтверждается, это не обязательно.
2. Используемое в теории управления преобразование разностного уравнения к форме с нильпотентной матрицей приводит за конечное число шагов при с = 0 к нулю, а при с ? 0 - не к решению, а смещенному, по терминологии [7], вектору.
3. Заданный спектр достигается изменением элементов одной из строк самой матрицы А, в теории управления изменяют строку из элементов характеристического полинома матрицы Фробениуса, получаемую преобразованием А.
4. Существуют значения х0, с которыми число m равно 1, 2, …, k - 1, в частности, m = k - 1 при х0 = с.
Заключение
Метод точного итерационного решения СЛАУ за конечное число шагов, обладая вычислительной процедурой итерационных в общепринятом смысле методов типа Якоби, Зейделя, можно назвать конечно-итерационным. Он, как и в теории управления, основан на задании спектра из единиц для матрицы СЛАУ или нулей для матрицы итерационного уравнения [8, 9], но с главным отличием, позволяющим решать не только однородное уравнение, но и неоднородное.
Преобразование СЛАУ к виду с унипотентной матрицей достигается, по терминологии теории управления, обратной связью по первой разности искомого вектора, которое математически есть частный случай канонической формы одношагового двухслойного итерационного метода. Его оценки еще впереди, но уже полученные результаты сравнения на примере СЛАУ третьего порядка с таким нестационарным итерационном методом, как метод сопряженных градиентов, демонстрируют более высокую точность.
Вопросы применения метода с подробным пояснением будут рассмотрены отдельно для наглядности на примере СЛАУ второго порядка с, иллюстрацией вывода формул Крамера в аналитическом виде в результате одной или двух итераций.
Список литературы
1. Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. М.: Физматгиз, 1963.
2. Strang G. Linear Algebra and Its Applications. - Academic Press, New York, 1976. Перевод: Стренг Г. Линейная алгебра и ее применения. - М.: Мир, 1980.
3. Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978.
4. Demmel W.D. Applied Numerical Linear Algebra. - Society for Industrial and Applied Mathematics, Philadelphia, 1997. Перевод: Деммель Дж. Вычислительная линейная алгебра. - М.: Мир, 2001.
5. Квакернаак Х., Сиван Р. Линейные оптимальные системы управления. - М.: Мир, 1977.
6. Rolf Isermann. Digital Control Systems. - Springer-Verlag, Berlin, Heidelberg, 1981. Перевод: Изерман Р. Цифровые системы управления: Пер. с англ. - М.: Мир, 1984.
7. Первозванский А.А. Курс теории автоматического управления. - М.: Наука, 1987.
8. Iskhakov, A., Pospelov, V. and Skovpen, S. (2012) Non-Frobenius Spectrum-Transformation Method. Applied Mathematics, 3, 1471-1479.
9. Iskhakov, A. and Skovpen, S. (2015) A Direct Transformation of a Matrix Spectrum. Journal of Progressive Research in Mathematics, 5, 463-481.
10. Iskhakov, A. and Skovpen, S. (2018) Exact Solution of a Linear Difference Equation in a Finite Number of Steps. Applied Mathematics, 9, 287-290.