Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Итерационные методы решения систем линейных алгебраических уравнений

Покупка
Новинка
Артикул: 896930.01.99
Доступ онлайн
798 ₽
В корзину
Соответствует содержанию направлений бакалаврской подготовки 01.03.02 «Прикладная математика и информатика». Рассматривается задача решения систем линейных алгебраических уравнений. Разбираются итерационные методы решения данной задачи: стационарные и нестационарные. Подробно рассматривается метод простых итераций: формулируются и доказываются теоремы о его сходимости, описываются способы приведения системы линейных уравнений к виду, удобному для итераций. Разбирается метод Якобы, метод итераций Зейделя и метод релаксаций, как частные случаи метода простых итераций. Доказываются теоремы о сходимости данных методов. В качестве нестационарных методов решения систем линейных алгебраических уравнений приводится метод Ричардсона, градиентный метод и метод сопряженных направлений. Рассматриваются базовые методы предобусловливания для ускорения итерационного процесса. В пособии представлен раздел с описанием лабораторной работы: формулируется задание и возможные исследования, представлены варианты и примеры выполнения. Предназначено для студентов, изучающих дисциплину «Численные методы», а также для преподавателей и инженеров, деятельность которых связана с вопросами вычислительной математики.
Курц, В. В. Итерационные методы решения систем линейных алгебраических уравнений : учебное пособие / В. В. Курц, С. Б. Добрецова, И. Е. Ануфриев. - Санкт-Петербург : ПОЛИТЕХ-ПРЕСС, 2025. - 72 с. - ISBN 978-5-7422-8862-6. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2286707 (дата обращения: 19.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
Министерство науки и высшего образования Российской Федерации
САНКТ-ПЕТЕРБУРГСКИЙ
ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ПЕТРА ВЕЛИКОГО
Физико-механический институт
Высшая школа прикладной математики и вычислительной физики
В. В. Курц
С. Б. Добрецова
И. Е. Ануфриев
ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ
ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ
Учебное пособие
Санкт-Петербург


ББК 22.143я73
K93
Р е ц е н з е н т ы:
Кандидат физико-математических наук,
доцент ВШ ПМ и ВФ СПбПУ А. В. Музалевский
Кандидат физико-математических наук,
научный сотрудник ИПМ им. М. В. Келдыша РАН А. А. Чечина
Курц В. В. Итерационные методы решения систем линейных алгебраических
уравнений : учеб. пособие / В. В. Курц, С. Б. Добрецова, И. Е. Ануфриев.  СПб. :
ПОЛИТЕХ-ПРЕСС, 2025.  72 с.
Соответствует содержанию направлений бакалаврской подготовки 01.03.02 ¾Прикладная математика и информатика¿.
Рассматривается задача решения систем линейных алгебраических уравнений. Разбираются итерационные методы решения данной задачи: стационарные и нестационарные.
Подробно рассматривается метод простых итераций: формулируются и доказываются теоремы о его сходимости, описываются способы приведения системы линейных уравнений
к виду, удобному для итераций. Разбирается метод Якобы, метод итераций Зейделя и
метод релаксаций, как частные случаи метода простых итераций. Доказываются теоремы о сходимости данных методов. В качестве нестационарных методов решения систем
линейных алгебраических уравнений приводится метод Ричардсона, градиентный метод
и метод сопряженных направлений. Рассматриваются базовые методы предобусловливания для ускорения итерационного процесса. В пособии представлен раздел с описанием
лабораторной работы: формулируется задание и возможные исследования, представлены
варианты и примеры выполнения.
Предназначено для студентов, изучающих дисциплину ¾Численные методы¿, а также
для преподавателей и инженеров, деятельность которых связана с вопросами вычислительной математики.
Табл. 2. Ил. 27. Библиогр.: 16 назв.
Печатается по решению
Совета по издательской деятельности Ученого совета
Санкт-Петербургского политехнического университета Петра Великого.
© Курц В. В., Добрецова С. Б.,
Ануфриев И. Е., 2025
ISBN 978-5-7422-8862-6
doi: 10.18720/SPBPU/2/id25-5
© Санкт-Петербургский политехнический
университет Петра Великого, 2025


Ministry of Science and Higher Education of the Russian Federation
PETER THE GREAT
ST. PETERSBURG POLYTECHNIC UNIVERSITY
Institute of Physics and Mechanics
Graduate School of Applied Mathematics and Computational Physics
V. V. Kurts
S. B. Dobretsova
I. E. Anufriev
ITERATIVE METHODS FOR SOLVING LINEAR SYSTEMS
Training manual
Saint Petersburg


ББК 22.143я73
K93
R e v i e w e r s:
Candidate (PhD) of Physics and Mathematics, associate professor
at the Graduate School of Applied Mathematics and Computational Physics
of SPbPU A. V. Muzalevskiy
Candidate (PhD) of Physics and Mathematics, researcher
at Keldysh Institute of Applied Mathematics of the RAS A. A. Chechina
Kurts V. V. Iterative methods for solving linear systems : training manual /
V. V. Kurts, S. B. Dobretsova, I. E. Anufriev.  St. Petersburg: POLYTECH-PRESS, 2025. 
72 p.
The training manual corresponds to the content of the Bachelor's degree majors 01.03.02
Applied Mathematics and Informatics.
The authors consider the problem of solving linear systems. Iterative methods of solving
this problem are analyzed: stationary and non-stationary. The xed point iteration method
is decsribed in detail. Theorems on its convergence are formulated and proved. Methods for
bringing a linear system to a form convenient for iterations are described. The Jacobi, the GaussSeidel and the relaxation methods are analyzed as special cases of the xed point iteration
method. Convergence theorems are formulated and proved. As non-stationary methods the
Richardson method, the gradient method, and the conjugate gradient method are described.
Basic preconditioning methods for speeding up the iterative process are presented. In addition,
the manual includes a section describing laboratory work. It contains the problem statement
and possible investigations, variants and examples.
It is intended for students studying the discipline Numerical methods as well as for
teachers and engineers whose area of interest is related to computational mathematics and
numerical methods.
Tables 2. Figures 27. References: 16 titles.
Printed by decision
of the Council on Publishing Activities of the Academic Board
of Peter the Great St. Petersburg Polytechnic University.
© Kurts V. V., Dobretsova S. B.,
Anufriev I. E., 2025
ISBN 978-5-7422-8862-6
doi: 10.18720/SPBPU/2/id25-5
© Peter the Great Saint Petersburg
Polytechnic University, 2025


ОГЛАВЛЕНИЕ
1. Характеристика итерационных методов решения систем линейных алгебраических уравнений
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2. Стационарные методы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.1. Метод простых итераций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.2. Сходимость стационарных итерационных процессов . . . . . . . . . . . . . .
25
3. Нестационарные методы
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
3.1. Полиномы Чебышева и их свойства . . . . . . . . . . . . . . . . . . . . . . . .
28
3.2. Метод Ричардсона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
3.3. Градиентный метод решения СЛАУ
. . . . . . . . . . . . . . . . . . . . . . .
35
3.4. Метод сопряженных градиентов . . . . . . . . . . . . . . . . . . . . . . . . . .
43
4. Предобусловливание для ускорения итерационных методов . . . . . . . .
46
4.1. Идея предобусловливания
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
4.2. Метод предобусловленных сопряженных градиентов . . . . . . . . . . . . . .
48
4.3. Предобусловливанние неполным разложением Холецкого . . . . . . . . . . .
49
4.4. Построение предобусловленного метода сопряженных градиентов для системы с пятидиагональной матрицей . . . . . . . . . . . . . . . . . . . . . . .
53
5. Критерии остановки в итерационных методах . . . . . . . . . . . . . . . . .
63
6. Описание лабораторной работы . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
6.1. Построение матрицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
6.2. Задание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
6.3. Возможные варианты исследований
. . . . . . . . . . . . . . . . . . . . . . .
67
6.4. Пример выполнения работы . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
Библиографический список
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
Приложение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


1.ХАРАКТЕРИСТИКА ИТЕРАЦИОННЫХ МЕТОДОВ РЕШЕНИЯ
СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ
В настоящее время существует огромное множество численных методов для решения
систем линейных алгебраических уравнений (СЛАУ), которые можно разделить на два
класса: прямые и итерационные. Прямые методы в общем случае позволяют найти ¾точное¿ (если не принимать во внимание вычислительную погрешность) решение системы
за O(n3) арифметических операций, где n  размерность системы, в то время как один
шаг итерационного метода требует выполнения O(n2) операций. Таким образом, итерационные методы становятся предпочтительными, если количество шагов для достижения
желаемой точности оказывается значительно меньше n.
В данном пособии мы разберем наиболее известные итерационные методы: стационарные и нестационарные. Приведем условия применимости методов и критерии остановки
для достижения требуемой точности. Кратко обсудим простейшие идеи предобусловливания, которые позволяют повысить скорость сходимости итерационного процесса.
Концепция итерационных методов заключается в следующем. Выбирается начальное
приближение x(0) ∈Rn и строится последовательность векторов {x(k)} по правилу
x(k) = Φk(A, b, x(k−1), . . . , x(k−r)),
(1.1)
пределом которой является точное решение x∗системы линейных алгебраических уравнений
Ax = b.
(1.2)
Процесс построения последовательности может быть остановлен тогда, когда найдено
решение задачи (1.2) с заданной точностью ϵ:


x(k) −x∗

 < ϵ.
Поскольку точное решение x∗неизвестно, то на практике применяются другие условия
остановки итерационного процесса, о которых мы поговорим далее.
Приведем классификационные признаки итерационных методов решения СЛАУ:
1. Если в выражении для функции Φk значение r равно 1, то метод называется одношаговым, если r > 1  многошаговым.
2. Если
функция
Φk
является
линейной
относительно
всех
x(i)
(i = k −1, k −2, . . . , k −r), то метод называется линейным, в противном случае 
нелинейным.
3. Если функция Φk зависит от k, то метод называется нестационарным, иначе 
стационарным, таким образом, вместо Φk можно просто писать Φ.
В данном пособии будем рассматривать линейные одношаговые методы. Канонический
вид таких методов представляет собой выражение
Bk
x(k+1) −x(k)
αk
+ Ax(k) = b,


где αk, Bk  канонические параметры, которые в общем случае зависят от k. Если αk =
α, Bk = B, то линейный одношаговый метод называют стационарным. Если хотя бы один
из канонических параметров зависит от номера итерации k, то метод является нестационарным.
Итерационный метод (1.3) называется явным, если известно B−1
k , например, при Bk =
E:
x(k+1) = x(k) −αk(Ax(k) −b).
Также
Bk
может
быть
диагональной
матрицей.
Матрицу
Bk
называют
предобусловливателем и подбирают так, чтобы повысить скорость сходимости метода.
При изучении итерационных методов решения СЛАУ возникают следующие вопросы.
1. Как построить последовательность {x(k)}?
2. При каких условиях последовательность {x(k)} будет сходиться к точному решению
исходной задачи (1.2)?
3. Когда
остановить
итерационный
процесс,
чтобы
получить
решение
с заданной точностью?
Ответы на эти вопросы будут даны в разделах данного пособия.
2.СТАЦИОНАРНЫЕ МЕТОДЫ
2.1.Метод простых итераций
Идея метода простых итераций для решения СЛАУ заключается в приведении исходной системы к виду, удобному для итераций, эквивалентным образом:
Ax = b ⇔x = Cx + g,
(2.1)
где C и g  некоторые новые матрица и вектор. Иными словами, если исходная система
имеет единственное решение x∗(det(A)̸ = 0), то и система x = Cx + g будет иметь то
же самое единственное решение x∗, и наоборот. Далее выбирается произвольный вектор
x(0) ∈Rn и строится последовательность по правилу
x(k+1) = Cx(k) + g, k = 0, 1, . . . .
(2.2)
Если последовательность x(k) сходится, то ее предел есть решение системы x = Cx +
g, а значит, и решение исходной системы Ax = b. Вопрос приведения к виду, удобному
для итераций, рассмотрим далее. Сформулируем условия, обеспечивающие сходимость
последовательности x(k).
2.1.1.Достаточные условия сходимости метода
простых итераций
Теорема 1. Если ∥C∥< 1, то:
1) существует единственное решение задачи (2.1);


2) итерационная последовательность, порождаемая формулой (2.2), сходится к этому
решению при произвольном выборе x(0) ∈Rn;
3) справедливы оценки погрешности:


x∗−x(k)

 ≤
∥C∥
1 −∥C∥


x(k) −x(k−1)

 ;
(2.3)


x∗−x(k)

 ≤
∥C∥k
1 −∥C∥


x(1) −x(0)

 .
(2.4)
Доказательство. Из
формулы
(2.2)
следует,
что
x(k+1)
−
x(k)
=
= C(x(k) −x(k−1)). Воспользуемся свойством для матричной и векторной нормы, которые
согласованы между собой:


x(k+1) −x(k)

 ≤∥C∥


x(k) −x(k−1)

 .
Запишем следующую цепочку преобразований:


x(k+m) −x(k)

 =
=


x(k+m) −x(k+m−1) + x(k+m−1) −. . . −x(k+1) + x(k+1) −x(k)

 ≤
≤


x(k+m) −x(k+m−1)

 + . . . +


x(k+2) −x(k+1)

 +


x(k+1) −x(k)

 ≤
≤∥C∥m 

x(k) −x(k−1)

 + . . . + ∥C∥2 

x(k) −x(k−1)

 + ∥C∥


x(k) −x(k−1)

 =
= ∥C∥(1 −∥C∥m)
1 −∥C∥


x(k) −x(k−1)

 ≤
≤
∥C∥k
1 −∥C∥(1 −∥C∥m)


x(1) −x(0)

 .
Рассмотрим крайние части в этой цепочке, зафиксируем m, значение k устремим к
бесконечности. За счет того, что ∥C∥< 1, правая часть неравенства стремится к 0, левая
также будет стремиться к 0. Из этого следует, что последовательность x(k) является фундаментальной, а значит, имеет предел x∗(поскольку Rn  полное пространство). Переходя
к пределу в равенстве (2.2), получим x∗= Cx∗+ g. Единственность x∗доказывается от
противного.
Справедливость оценок (2.3) и (2.4) следует из цепочки неравенств


x(k+m) −x(k)

 ≤∥C∥(1 −∥C∥m)
1 −∥C∥


x(k) −x(k−1)

 ≤
≤∥C∥k (1 −∥C∥m)
1 −∥C∥


x(1) −x(0)

 ,
если зафиксировать k, а значение m устремить к бесконечности.
В дополнение к этой теореме можно сделать ряд замечаний.
1. Норма в оценках (2.4) и (2.3) может быть любой. На практике удобно использовать
первую или бесконечную нормы.
2. Априорная оценка (2.4) является грубее апостериорной (2.3), поэтому на практике
отдается предпочтение второй. Априорная оценка позволяет вычислить число итераций


Доступ онлайн
798 ₽
В корзину