2). Сортировка обменом (методом "пузырька")

В основе алгоритма лежит обмен соседних элементов массива. Каждый элемент массива, начиная с первого, сравнивается со следующим и если он больше следующего, то элементы меняются местами. Таким образом, элементы с меньшим значением продвигаются к началу массива (всплывают), а элементы с большим значением – к концу массива (тонут), поэтому этот метод иногда называют "пузырьковым". Этот процесс повторяется на единицу меньше раз, чем элементов в массиве.

Пример. Используя сортировку обменом, упорядочить по возрастанию элементы одномерного массива, состоящего из 5 целых чисел. Для демонстрации процесса сортировки программа выводит массив после каждого цикла обменов.

Program Sort;

Const

size=5;

Var

a: array[1.. size ] of integer;

i: integer; { счетчик циклов }

k: integer; { текущий индекс элемента массива }

buf: integer;

Begin

writeln (′Сортировка массива пузырьковым методом.′ );

write (′Введите′ ֽ size:3 ֽ′ целых в одной строке ′ );

writeln (′через пробел и нажмите <Enter>′ );

for k:=1 to size do read (a [k] );

writeln (′Сортировка ′ );

for i:=1 to size-1

do Begin

for k:=1 to size-1

do begin

if a[k]> a[k+1]

then begin

{ поменяем местами a[k] и a[k+1] }

buf:= a[k];

a[k]:= a[k+1];

a[k+1]:= buf;

end;

end;

for k:=1 to size do write(a[k], ′ ′ );

writelen;

end;

writeln (′ Массив отсортирован. ′ );

end.

Решение системы линейных уравнений численными методами.

Решение систем линейных алгебраических уравнений - одна из основных задач вычислительной линейной алгебры. Хотя задача решения системы линейных уравнений сравнительно редко представляет самостоятельный интерес для приложений, от умения эффективно решать такие системы часто зависит сама возможность математического моделирования самых разнообразных процессов с применением ЭВМ. Значительная часть численных методов решения различных (в особенности - нелинейных) задач включает в себя решение систем линейных уравнений как элементарный шаг соответствующего алгоритма.

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

Итерационные методы применяют главным образом для решения задач большой размерности, когда использование прямых методов невозможно из-за ограничений в доступной оперативной памяти ЭВМ или из-за необходимости выполнения чрезмерно большого числа арифметических операций.

Прямые методы решения систем линейных уравнений.

Метод Гаусса.

Одним из самых распространенных методов решения систем линейных уравнений является метод Гаусса. Этот метод (который также называют методом последовательного исключения неизвестных) известен в различных вариантах уже более 2000 лет.

Постановка задачи.

Пусть дана система из n линейных уравнений с n неизвестными

х_1, х₂,,х₃…, х_n

(1)

Числа a_ik- называются коэффициентами системы (1), а числа , ,…, - свободными членами. Система (1) называется однородной, если = =…= =0

Матрица А=

называется матрицей системы (или матрицей коэффициентов) (1), а ее определитель |А| - определителем системы (1).

Столбец В =

называется столбцом свободных членов. Если присоединить к матрице А столбец свободных членов, то получим матрицу , которая называется расширенной матрицей системы:

=

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

Две системы линейных уравнений с одним и тем же числом неизвестных называются эквивалентными, если они или обе несовместны, или обе совместны и имеют одни и те же решения.

Элементарными преобразованиями системы линейных уравнений называются следующие три типа преобразований:

1) перестановка двух уравнений системы;

2) умножение обеих частей уравнения системы на любое отличное от нуля число;

3) прибавление (вычитание) к обеим частям одного уравнения соответствующих частей другого уравнения, умноженных на любое число.

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

Метод Гаусса применяется для решения систем линейных уравнений, определитель матрицы А которых отличен от 0, такие системы совместны и имеют единственное решение.

Вычисления с помощью метода Гаусса заключаются в последовательном исключении неизвестных из системы, для преобразования ее к эквивалентной системе с верхней треугольной матрицей. Этот этап преобразований называется прямым ходом. На втором этапе, называемом обратным ходом, производятся вычисления значений неизвестных.

Схема единственного деления. Рассмотрим сначала простейший вариант метода Гаусса, называемый схемой единственного деления.

Прямой ход состоит из п - 1 шагов исключения.

1-й шаг. Целью этого шага является исключение неизвестного х\ из уравнений с номерами i = 2, 3, ..., п. Предположим, что коэффициент . Будем называть его главным (или ведущим) элементом 1-го шага.

Найдем величины (i = 2, 3, ..., n),

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

в которой и вычисляются по формулам:

, .

2-й шаг. Целью этого шага является исключение неизвестного из уравнений с номерами i= 3, 4, ..., n. Пусть а₂₂⁽¹⁾ 0, где a₂₂⁽¹⁾ - коэффициент, называемый главным (или ведущим) элементом 2-го шага. Вычислим множители 2-го шага

(i=3, 4, …, n) и вычтем последовательно из третьего, четвертого, ..., n-го уравнения системы второе уравнение, умноженное соответственно на В результате получим систему

Здесь коэффициенты и вычисляются по формулам

= -

Аналогично проводятся остальные шаги. Опишем очередной k-й шаг.

k:-й шаг. В предположении, что главный (ведущий) элемент k-ro шага отличен от нуля, вычислим множители k-го шага

и вычтем последовательно из (k + 1)-го, ..., n-го уравнений полученной на предыдущем шаге системы k-е уравнение, умноженное соответственно на

После (n-1)-го шага исключения получим систему уравнений:

матрица которой является верхней треугольной. На этом вычисления прямого хода заканчиваются.

Обратный ход. Из последнего уравнения системы находим . Подставляя найденное значение в предпоследнее уравнение, получим . Осуществляя обратную подстановку, далее последовательно находим . Вычисления неизвестных здесь проводятся по формулам

Заметим, что вычисление множителей, а также обратная подстановка требуют деления на главные элементы . Поэтому если один из главных элементов оказывается равным нулю, то схема единственного деления не может быть реализована. Однако, в ситуации, когда все главные элементы отличны от нуля, но среди них есть близкие к нулю, возможен неконтролируемый рост погрешности. Поэтому при получении решения системы линейных уравнений обычно производят оценку погрешности и затем уточнение решения.

Это производят следующим образом:

1. вычисляют для каждого уравнения системы невязки — разности между правой и левой частями системы, получающиеся после подстановки в уравнения приближенных значений неизвестных по формулам:

где приближенные значения неизвестных невязки - и свободные члены -

2) выписывают невязки в отдельный столбец;

3) считая столбец е столбцом свободных членов, снова решают по схеме Гаусса исходное уравнение, и получают поправки неизвестных;

4) находят уточненные значения неизвестных, прибавляя к приближенным значениям неизвестных соответствующие поправки

Пример. Дана система линейных уравнений третьего порядка. Решить систему методом Гаусса по схеме единственного деления.

Программа, реализующая метод Гаусса должна содержать следующие последовательно расположенные блоки:

1) ввод исходных данных (матрицы А и столбца свободных членов В);

2) прямой ход, состоящий в делении на главные (ведущие) коэффициенты и последовательном исключении неизвестных с целью приведения матрицы А к верхнему треугольному виду;

3) обратный ход, состоящий в вычислении неизвестных, начиная с последнего;

4) вывод полученного решения.

Program gauss;

{Решение системы лин. уравнений третьего порядка методом Гаусса}

var a:array [1..3.1..3] of real;

b:array [1..3] of real;

x:array [1..3] of real;

ij,k:integer;

d:real;

const n=3;

begin

writeln ('Введите матрицу А:');

for i:=l to n do

begin

{....................Ввод исходных данных....................}

for j:=l to n do

begin

write ('a[',i,’,’,j,']=');

readln( a[i,j]);

end;

end;

writeln ('Введите столбец свободных членов: ');

for i:=l to n do

begin

write('b[',i,']=');

readln (b[i]);

end;

{................Прямой ход.............}

for i:=l to n-1 do

begin

for k:=i+l to n do

begin

d:=a[k,i]/a[i,i];

for j:=i+l to n do

a[k,j]:=a[k,j]-a[I,j]*d;

b[k]:=b[k]-b[i]*d;

end;

end;

{................Обратный ход...........}

for i:=n downto 1 do

begin

for j:=i+l to n do

b[i]:=b[i]-a[i,j]*x[j];

x[i]:=b[i]/a[i,i];

end;

{..........................Вывод решения................}

writeln('Решение системы линейных уравнений:');

for i:=l to n do

writeln('X[',i,']=',x[i]:l:4);

readln;

end.