Метод Гаусса с выбором главного элемента. Организация параллельных программ как системы потоков, параллельное программирование с использованием TPL. Постановка задачи и анализ результатов. Алгоритм обработки исходных данных, разработка программного кода.
Аннотация к работе
Несмотря на то что задача решения именно системы линейных уравнений сравнительно редко представляет самостоятельный интерес для прикладных задач, то от умения эффективно решать данные системы часто зависит сама возможность математического моделирования самых разнообразных процессов с применением ЭВМ. Значительная часть численных методов решения различных, в особенности - нелинейных, задач включает в себя решение систем линейных уравнений как элементарный шаг соответствующего алгоритма. код программный гаусс поток С развитием вычислительной техники, увеличением математических расчетов появляются проблемы, которые заключаются в длительном времени выполнения вычислений и увеличении используемых ресурсов вычислительной машины. И программа, разработанная с использованием механизма потоков, представляемая как некоторое множество задач в рамках одного процесса, может быть выполнена быстрее за счет параллельного функционирования ее отдельных частей.LU-разложение - представление матрицы в виде произведения матриц , где - нижняя треугольная матрица с единичной диагональю, а - верхняя треугольная матрица с единичной диагональю. Определителем матрицы служит результат произведения элементов, расположенных на главной диагонали. Структура матриц и позволяет организовывать компактное размещение элементов этих матриц в памяти ЭВМ по мере их вычисления. На-ом шаге исключения в области памяти, где первоначально располагалась матрица , размещается матрица На втором этапе выполняют следующие действия: 1) Преобразуют правую часть по формулам прямого хода; необходимые вычисления коэффициенты берут из матрицы .Можно доказать, что существование LU-разложения для матрицы гарантирует, что и матрица допускает LU-разложение: главные миноры матриц и совпадают. (7) при матрице нижнетреугольной и - верхнетреугольной следует, что (8) Поскольку обе матрицы в правой части являются нижнетреугольными, то и их произведение также будет нижнетреугольной матрицей.Согласно источнику [5], вычисления с помощью метода Гаусса (который называют также методом последовательного исключения неизвестных) состоят из двух основных этапов: прямого хода и обратного хода. Прямой ход метода заключается в последовательном исключении неизвестных из системы для преобразования ее к эквивалентной системе с треугольной матрицей. Поделим первое уравнение на этот элемент, который назовем ведущим элементом первого шага: (12) Система (1) имеет матрицу вида: Дальше осуществляется работа с укороченной системой, т.к. входит только в 1-ое уравнение Если ведущий элемент второго шага , то из укороченной системы аналогично исключается неизвестное и получается матрица коэффициентов такого вида: Это система с верхней треугольной матрицей.Из источника [5] сказано, что может оказаться так, что система (1) имеет единственное решение, хотя какой либо из миноров матрицы равен нулю. В этом случае можно использовать метод Гаусса с выбором главного элемента. Выбор главного элемента по столбцу, когда на-ом шаге исключения в качестве главного элемента выбирают максимальный по модулю коэффициент при неизвестном в уравнениях с номерами . Затем уравнение, соответствующее выбранному коэффициенту, меняют местами с-ым уравнением системы, чтобы ведущий элемент занял место коэффициента .Понятие потока может быть использовано в качестве основного конструктивного элемента для построения параллельных программ в виде совокупности взаимодействующих потоков. Согласно [7], возможные типовые варианты таких соотношений на примере двух потоков p и q состоят в следующем (см. рисунок 1): Рисунок 1 - Варианты взаиморасположения траекторий одновременно исполняемых потоков (отрезки линий изображают фрагменты командных последовательностей потоков) выполнение потоков осуществляется строго последовательно, т. е. поток начинает свое выполнение только после полного завершения потока (однопрограммный режим работы ЭВМ - см. рисунок 1 пункт а); выполнение потоков может осуществляться одновременно, но в каждый момент времени могут исполняться команды только какого-либо одного потока (режим разделения времени или многопрограммный режим работы ЭВМ - см. рисунок 1 пункт б); Ситуация, когда два или более потоков используют разделяемый ресурс и конечный результат зависит от соотношения скоростей потоков, называется состязанием или гонками.Начиная с версии .NET 4.0, в Microsoft ввели новый подход к разработке многопоточных приложений, предусматривающий использование библиотеки параллельного программирования, которая называется TPL (Task Parallel Library - библиотека параллельных задач). С помощью типов из System.Threading.Tasks можно строить мелкомодульный масштабируемый параллельный код без необходимости напрямую иметь дело с потоками или пулом потоков.Ключевым классом в TPL является System.Threading.Tasks.Parallel. Этот класс поддерживает набор методов, которые позволяют осуществлять итерацию по коллекции данных, т.е. по объекту, реализующему интерфейс IENUMERABLE, в параллельном режиме. В документации .NET Framework 4.
План
Содержание
Введение
1. Обзор существующих методов решения задач
1.1 LU-разложение
1.2 LDU - разложение
1.3 Метод Гаусса
1.4 Метод Гаусса с выбором главного элемента
2. Основы параллельного программирования
2.1 Организация параллельных программ как системы потоков
2.2 Параллельное программирование с использованием TPL
2.2.1 Роль класса Parallel
2.2.2 Обеспечение параллелизма данных с помощью класса Parallel
2.2.3 Запросы Parallel LINQ (PLINQ)
2.2.4 Выполнение запроса PLINQ
2.2.5 Отмена запроса PLINQ
3. Алгоритммический анализ задачи
3.1 Постановка задачи, анализ исходных данных и результатов
3.2 Алгоритм обработки исходных данных
3.3 Алгоритм решения системы линейных алгебраических уравнений методом LDU-разложения
3.4 Алгоритм решения системы линейных алгебраических уравнений методом Гаусса