Московский Государственный Университет
Механико-математический факультет
Кафедра вычислительной механики
Курсовая работа
Сравнение и особенности различных решателей СЛАУ
Выполнил:
Студент 4 курса
Научный руководитель:
Кандидат физико-математических наук
Доцент кафедры вычислительной механики МГУ
Москва 2015
Введение……………………………………………………………….……….….…3
Цели и задачи……………………………………………………………….3
Актуальность………………………………………………………..…….…3
Особенности матриц СЛАУ……………………………………….….…..…4
Симметричность………………………………………………….……….4
Обусловленность…………………………………………….…...……..6
Особенности решения СЛАУ…………………………………….…………9
Сравнение прямых и итерационных методов……………….…..10
Прямые методы решения СЛАУ……………………………….….10
Итерационные методы решения СЛАУ……………………….10
Особенности прямых методов………………………………..…..11
Особенности итерационных методов………………….……..11
Построение системы наилучшего выбора решателя…….…..13
Отличия расчетов на GPU и CPU……….………………………...15
Предобуславливание………………………………………….……….18
Заключение………………………………………………………….………………20
Проведенная работа……………………………….…………………..20
Список используемой литературы……………………….…………….21
Введение
Цели и задачи.
• Проанализировать особенности решателей и их актуальность.
• Сравнить их по различным характеристикам.
• Продемонстрировать сильные и слабые стороны решателей.
• Рассмотреть зависимость по разным начальным данным.
• Сделать систему выбора решателей по начальным данным с учетом их особенностей, для различных устройств.
Актуальность.
• Возможность в короткие сроки, и с максимальной эффективностью решать поставленные задачи.
• Выявление ошибок, расчетный процесс без человеческого фактора.
• Развитие технологий и вычислительных машин создаёт большую среду для модернизаций и улучшений решатели СЛАУ, что в свою очередь многим может помочь сэкономить время, увеличить качество и производительность результатов вычислений, и даже дать возможность решать задачи, ранее невыполнимые.
Особенности матриц СЛАУ
Симметричность.
Матрицы СЛАУ могут иметь самые различные особенности.
Например, симметричность и +/- определенность.
Симметричная, Несимметричная,
неразреженная, малого порядка,
положительно отрицательно
определённая определённая
Симметричность: 
aij = aji или A=Aт. Симметричная матрица A размерностью k*k называется положительно определённой, если 
Rk : xтAx > 0.
Для любой симметричной матрицы из Rk (с вещественными элементами) выполнено:
1. имеет собственные значения;
2. её собственные векторы, соответствующие разным собственным значениям, ортогональны друг другу;
3. из её собственных векторов всегда можно составить ортонормированный базис;
4. матрицу A можно привести к диагональному виду: A = QDQт, где Q — ортогональная матрица, столбцы которой содержат ортонормированный базис из собственных векторов, а D — диагональная матрица с собственными значениями матрицы A на диагонали;
5. Если у симметричной матрицы A единственное собственное значение λ, то она имеет диагональный вид: A = λE, где E — единичная матрица, в любом базисе.
Геометрически представить решение СЛАУ от трёх переменных можно как пересечение плоскостей в одной точке, которая и является решением.
Пусть L — линейное пространство над полем R. A: L -> L линейное отображение. Собственным вектором линейного преобразования A называется такой ненулевой вектор 
, что для некоторого λ 
: Ax = λ x. Собственным значением линейного преобразования матрицы A называется такое число 
, для которого существует собственный вектор, т. е. уравнение Ax = λ x имеет ненулевое решение при .
Обусловленность.
Ещё одной особенностью является обусловленность матрицы. Это свойство чувствительности системы к начальным данным. Даже у матриц с маловидимыми различиями может быть большая разница в чувствительности.
Геометрически можно представить это на примере действия нашего оператора на круг. Из курса линейной алгебры мы знаем, что результатом будет совокупность поворотов и растяжений (повернутый эллипс). Число обусловленности тут есть отношение большей полуоси к меньшей. Наилучшее число обусловленности (наименьшее, не превосходящее единицу) будет при повороте (погрешность правой части совпадает с погрешностью решения).
µ=b/a
Пусть линейный оператор А: LK -> MK . Дано нормированное пространство Rk . Линейный оператор A действует в этом нормированном пространстве. Число обусловленности нашего линейного оператора A имеет вид: µ = ||A||*||A-1||.
Как мы видим, число обусловленности и выбор нормы связаны.
Предположим что наша матрица СЛАУ и правая часть заданы неточно. То погрешность матрицы – δA,
Погрешность правой части – δf.
Покажем что для погрешности δx
реализована оценка: ||δA||*||A-1||<1;
и при δA=0:
При этом решение уравнения Ax = f не при всех f одинаково чувствительно к возмущению δf правой части.
Свойства:
1) 
где 
= 1;
2) 
;
3) 
, где 
собственные значения матрицы A;
4) 
, при численном решении систем с плохо обусловленными матрицами (
103) возможно сильное накопление погрешностей, что следует из оценки для погрешности dx.
Особенности решения СЛАУ
Сравнение прямых и итерационных методов
Прямые методы решения СЛАУ.
В прямых методах точное решение находится за один проход алгоритма (определённое конечное число арифметических действий). Например, прямыми методами являются методы:
Гаусса;
• LU разложение;
• Вращений;
• Крамера;
• Обратных матриц;
• Прогонки;
• Квадратного корня (Холецкого) и т. д. .
Итерационные методы решения СЛАУ.
Итерационные методы заключены в том, что при решении СЛАУ указывается рекуррентное соотношение. Оно по заданному (произвольно) «нулевому» приближению решения, позволяет вычислить 1,…,m-e приближения. Например, итерационными являются методы:
• Якоби (МПИ);
• Зейделя;
• релаксации (верхней);
• многосеточный;
• сопряженных градиентов;
• обобщенных минимальных невязок и т. д..
Особенности прямых методов.
• Прямые методы дают более точное решение и делают один проход;
• важна область применения (бывают задачи, в которых итерационные методы расходятся, в этих случаях остается использовать только прямые методы);
• прямые методы решения СЛАУ более выгодно использовать, если необходимо решать много одинаковых систем с различными правыми частями, или если матрица А не является положительно-определенной;
• неэффективны при больших матрицах системы из-за большого количества арифметических операций и полного хранения матрицы в памяти (или вовсе невозможны из-за ограниченности оперативной памяти);
• теряют свойство разреженности при разреженных матрицах;
• примерное количество арифметических операций О(n3).
Особенности итерационных методов.
• Итерационные методы, начиная с некоторой большой величины матриц, в результате используют меньше времени и ресурсов ЭВМ;
• они так же в меньшей степени используют структуру матрицы (прямые методы, используя ненулевой элемент, превращается в ненулевой, в то время как итерационный процесс помогает сохранить свойство разреженности);
• итерационные методы делают вычисления до определенной заданной точности, поэтому при некотором округлении можно значительно сократить время выполнения и затраченные ресурсы;
• эффективны при разреженных матрицах и больших матрицах системы;
• но всё это с подходящими условиями (обусловленность, симметричность, положительная определённость и т. д.).
Пример эффективности итерационного метода при больших размерностях матриц :
Рис. 1.
Зависимость размерности матрицы от времени при положительно определённых симметричных матрицах.
Использование итерационных методов(Зейделя и CG) и прямых методов(Гаусса и Холецкого).
Построение системы наилучшего выбора решателя
При построении блок-схемы следует учитывать отличительные особенности прямых и итерационных методов, перечисленных в пункте «Сравнение прямых и итерационных методов», а так же наиболее встречающиеся для большинства современных задач данные и проверочные расчетные данные.
Далее подбираем решатель в зависимости от начальных данных. Например, при выборе прямого:
Из рис.1 видно, что при А(2000) время расчета итерационного метода гораздо меньше (чем у прямого), что увеличивает его приоритет выбора.
Отличия расчетов на GPU и CPU.
Затем, серьезным фактором выбора итерационного решателя является устройство выполнения расчетов (CPU или GPU).
Графический процессор (graphics processing unit, GPU) — отдельное устройство персонального компьютера, выполняющее графический рендеринг. Современные графические процессоры очень эффективно обрабатывают и отображают компьютерную графику.
Отличительными особенностями по сравнению с ЦП являются: архитектура, максимально нацеленная на увеличение скорости расчёта текстур и сложных графических объектов; ограниченный набор команд.
Центральный процессор (или центральное процессорное устройство — ЦПУ; central processing unit, CPU) — электронный блок либо интегральная схема (микропроцессор), исполняющая машинные инструкции (код программ), главная часть аппаратного обеспечения компьютера или программируемого логического контроллера. Иногда называют микропроцессором или просто процессором.
Главными характеристиками ЦПУ являются: тактовая частота, производительность, энергопотребление, нормы литографического процесса, используемого при производстве (для микропроцессоров) и архитектура.
CPU GPU
Коротко об их сравнении:
• ядра CPU сделаны для выполнения одного потока поочередных операций с максимальной производительностью, в то время как GPU для быстрого выполнения большого числа параллельно выполняемых потоков операций. В этом и заключена основная разница;
• в CPU технологиях стремятся увеличить число выполняемых параллельно операций. Работа направлена на улучшение отдельного алгоритма. GPU же изначально имеет распараллеленную работу;
• GPU от CPU отличаются и в принципе доступа к памяти. GPU при записи пикселя в буфер через некоторое время будет записан и соседний с ним пиксель. Поэтому, чипу нет необходимости в кэш-памяти большого размера.
Пример расчетов больших матриц методом BCG на
GPU(GeForce GTX 780 – Объём видеопамяти (Мб) 3072, ядрo(MHz) 863, память (MHz) 6008)
И CPU (Intel Core 2 Quad - Частота ЦП: 2,33—3,20 ГГц, Частота FSB: 1066—1600 МГц):
Рис. 2.
Соотношение количества итераций для решения определенной матрицы с заданной одинаково точностью решения, в зависимости от количества элементов матрицы(тыс.).
Предобуславливатели.
Предобуславливание— процесс преобразования условий задачи для её более корректного численного решения.
Предобуславливание обычно связано с уменьшением числа обусловленности задачи. Предобуславливаемая задача после этого обычно решается итерационным методом.
Решается предобусловленная система P-1(Ax-b)=0 или AP-1Px=b, вместо исходной Ax-b=0.
Реализуется предобусловленная система через форму AP-1y=b, где y удовлетворяет условию Px=y.
Результатом вычислений будет то же решение, что при Ax=b,
до тех пор пока матрица-предобуславливатель P невырождена(Det(P)≠0).
Для квадратной матрицы P над полем R,невырожденность эквивалентна каждому из следующих условий:
· P обратима, то есть существует обратная матрица;
· строки (столбцы) матрицы P линейно независимы;
· ранг матрицы равен её размерности.
Матрица порядка n заведомо невырождена, если это:
· диагональная матрица с ненулевыми диагональными элементами;
· верхняя треугольная матрица с ненулевыми диагональными элементами;
· нижняя треугольная матрица с ненулевыми диагональными элементами;
· унитреугольная матрица (т. е. верхние треугольные матрицы у которых диагональные элементы равны 1).
Предобуславливание делается для уменьшения числа обусловленности системы, что в свою очередь увеличивает скорость сходимости итерационных процессов.
Таким образом:
• P должна быть по возможности близка к A;
• P должна быть легко вычислима;
• P должна быть легко обратима.
Наибольшую пользу работы с предобуславливанием для СЛАУ являются метод сопряженных градиентов, метод бисопряженных градиентов и метод обобщенных минимальных невязок.
Так же учесть то, что на построение хороших предобуславливателей может уходить много времени, однако это может принести результат, который превзойдет затраты. Но это не всегда удается добиться. Следовательно, существует метод отбора систем, для которых следует это делать, а для каких не стоит.
Соответственно при выборе GPU и CPU сразу следует учесть распараллелизацию процесса и способ представления данных в памяти компьютера (например, прямые решатели очевидным образом плохо подходят для решения на GPU).
Следует одновременно учесть симметричность, +/-определенность, метод хранения матрицы в памяти, разреженность матрицы и др. Например при A=Aт и A>0 для разреженных матриц большого порядка хорошо подходит CG, а для несимметричных матриц быстрее решает BCG. Но это без учета предобуславливателей и метода хранения матриц. Если добавить подобных особенностей(например как хранение матрицы), то более подходящим может оказаться и другой решатель, например такой как FGMRes или GMRES:.
Заключение
Выбор решателя в некоторых задачах может быть прост и очевиден. Но иногда это большая проблема, решение которой нужно делать как технически (тестирование разных решателей на одном устройстве по различным признакам и с различными данными), так и аналитически(рассматривать алгоритмы, искать необходимые особенности и даже возможности некоторых комбинаций).
Проведённая работа.
1. Проанализированы особенности решателей и их актуальность.
2. Продемонстрированы их сильные и слабые стороны.
3. Выполнено сравнение некоторых решателей с примерами по разным признакам.
4. Построена начальная модель-схема системы выбора решателя.
Используемая литература.
1. Численные методы / . – М.: Наука, 1975. – 468 с.
2. Методы решения СЛАУ большой размерности. / ., .–Новосибирск: Изд-во НГТУ, 2000. – 70 с.
3. Решение систем линейных уравнений / С. К. Годунов.– Новосибирск: Наука, 1980. – 250 с.
4. Бутюгин Д. С., , и др. Krylov: библиотека алгоритмов и программ для решения СЛАУ // Современные проблемы математического моделирования. Математическое моделирование, численные методы и комплексы программ. Сборник трудов Всероссийских научных молодёжных школ. Ростов-на-Дону: Изд-во Южного федерального университета, 2009, 110-128.
5. Численное решение больших разреженных систем уравнений / Дж. Лиу. – М.: Мир, 1984. – 390 с.
6. NVIDIA/ object/tesla-gpu-accelerated-libraries; http://www. /
7. Абаффи Й., атематические методы для линейных и нелинейных уравнений: проекционные ABS - алгоритмы. — М.: Мир, 1996.
8. Ильин неполной факторизации для решения линейных систем. — М.: Физматлит, 1995.
9. Писсанецки С. Технология разреженных матриц. — М.: Мир, 1988.
