Системы линейных уравнений

Вычислительные факторы

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

В матричном обозначении общая проблема принимает следующую форму: Учитывая две матрицы A и b, действительно там существует уникальный матричный x, так, чтобы A xb или x Ab?

Это поучительно, чтобы рассмотреть пример 1 на 1. Например, делает уравнение

7x = 21

имеет уникальное решение?

Ответ, конечно, является да. Уравнение имеет уникальное решение x = 3. Решение легко получено делением:

x = 21/7 = 3.

Решение обычно не получается путем вычисления инверсии 7, который является 7–1 = 0.142857..., и затем умножение 7–1 21. Это было бы, больше работают и, если 7–1 представлен конечному числу цифр, менее точных. Подобные факторы применяются к наборам линейных уравнений с больше чем одним неизвестным; MATLAB® решает такие уравнения, не вычисляя инверсию матрицы.

Несмотря на то, что это не стандартное математическое обозначение, MATLAB использует терминологию деления, знакомую в скалярном случае, чтобы описать решение общей системы одновременных уравнений. Два символа деления, наклонная черта,/, и обратная косая черта, \, соответствуют этим двум функциям MATLAB mrdivide и mldivide. Эти операторы используются для двух ситуаций, где неизвестная матрица появляется слева или право на матрицу коэффициентов:

x = b/A

Обозначает решение матричного уравнения xA = b, полученное использование mrdivide.

x = A\b

Обозначает решение матричного уравнения Ax = b, полученное использование mldivide.

Думайте о “делении” обеих сторон уравнения Ax = b или xA = b A. Матрица коэффициентов A всегда находится в “знаменателе”.

Условия совместимости размерности для x = A\b потребуйте этих двух матриц A и b иметь одинаковое число строк. Решение x затем имеет одинаковое число столбцов как b и его размерность строки равна размерности столбца A. Для x = b/A, ролями строк и столбцов обмениваются.

На практике линейные уравнения формы Ax = b происходят более часто, чем те из формы xA = b. Следовательно, обратная косая черта используется намного более часто, чем наклонная черта. Остаток от этого раздела концентрируется на операторе обратной косой черты; соответствующие свойства оператора наклонной черты могут быть выведены из идентичности:

(b/A)' = (A'\b').

Матрица коэффициентов A не должно быть квадратным. Если A имеет размер m-by-n, затем существует три случая:

m = n

Квадратная система. Ищите точное решение.

m> n

Сверхрешительная система, большим количеством уравнений, чем неизвестные. Найдите решение методом наименьших квадратов.

m <n

Недоопределенная система, меньшим количеством уравнений, чем неизвестные. Найдите основное решение с в большей части m ненулевые компоненты.

Mldivide Алгоритм

mldivide оператор использует другие решатели, чтобы обработать различные виды содействующих матриц. Различные случаи диагностированы автоматически путем исследования матрицы коэффициентов. Для получения дополнительной информации смотрите раздел “Algorithms” mldivide страница с описанием.

Общее решение

Общее решение системы линейных уравнений Axb описывает все возможные решения. Можно найти общее решение:

  1. Решение соответствующей гомогенной системы Ax = 0. Сделайте это использование null команда, путем ввода null(A). Это возвращает основание для пробела решения к Ax = 0. Любое решение является линейной комбинацией базисных векторов.

  2. Нахождение конкретного решения неоднородной системы Ax =b.

Можно затем записать любое решение Axb как сумма конкретного решения Ax =b, от шага 2, плюс линейная комбинация базисных векторов от шага 1.

Остальная часть этого раздела описывает, как использовать MATLAB, чтобы найти конкретное решение Ax =b, как на шаге 2.

Квадратные системы

Наиболее распространенная ситуация включает квадратную матрицу коэффициентов A и один правый вектор-столбец стороны b.

Несингулярная матрица коэффициентов

Если матричный A несингулярно, затем решение, x = A\b, одного размера с b. Например:

A = pascal(3);
u = [3; 1; 4];
x = A\u

x =
      10
     -12
       5

Это может быть подтверждено тот A*x точно равно u.

Если A и b являются квадратными и тот же размер, x= A\b также что размер:

b = magic(3);
X = A\b

X =
      19    -3    -1
     -17     4    13
       6     0    -6

Это может быть подтверждено тот A*x точно равно b.

Оба из этих примеров имеют точные, целочисленные решения. Это вызвано тем, что матрица коэффициентов была выбрана, чтобы быть pascal(3), который является (несингулярной) матрицей полного ранга.

Сингулярная матрица коэффициентов

A квадратной матрицы сингулярен, если он не имеет линейно независимых столбцов. Если A сингулярен, решение Ax = b или не существует или не уникален. Оператор обратной косой черты, A\b, выдает предупреждение если A почти сингулярно или если это обнаруживает точную сингулярность.

Если A сингулярен и Ax =, b имеет решение, можно найти конкретное решение, которое не уникально путем ввода

P = pinv(A)*b

pinv(A) псевдоинверсия A. Если Ax = b не имеет точного решения, то pinv(A) возвращает решение методом наименьших квадратов.

Например:

A = [ 1     3     7
     -1     4     4
      1    10    18 ]

сингулярно, когда можно проверить путем ввода

rank(A)

ans =

     2

Поскольку A не является полным рангом, он имеет некоторые равные нулю сингулярные значения.

Точные решения. Для b =[5;2;12], уравнение Ax = b имеет точное решение, данное

pinv(A)*b

ans =
    0.3850
   -0.1103
    0.7066

Проверьте тот pinv(A)*b точное решение путем ввода

A*pinv(A)*b

ans =
    5.0000
    2.0000
   12.0000

Решения методом наименьших квадратов. Однако, если b = [3;6;0], Ax = b не имеет точного решения. В этом случае, pinv(A)*b возвращает решение методом наименьших квадратов. Если вы вводите

A*pinv(A)*b

ans =
   -1.0000
    4.0000
    2.0000

вы не возвращаете исходный вектор b.

Можно определить, имеет ли Ax =b точное решение путем нахождения, что строка уменьшала форму эшелона расширенной матрицы [A b]. Чтобы сделать так для этого примера, войти

rref([A b])
ans =
    1.0000         0    2.2857         0
         0    1.0000    1.5714         0
         0         0         0    1.0000

Поскольку нижний ряд содержит все нули за исключением последней записи, уравнение не имеет решения. В этом случае, pinv(A) возвращает решение методом наименьших квадратов.

Сверхрешительные системы

В этом примере показано, как со сверхрешительными системами часто сталкиваются в различных видах аппроксимирования кривыми к экспериментальным данным.

Количество y измеряется в нескольких различных значениях времени t произвести следующие наблюдения. Можно ввести данные и просмотреть их в таблице со следующими операторами.

t = [0 .3 .8 1.1 1.6 2.3]';
y = [.82 .72 .63 .60 .55 .50]';
B = table(t,y)
B=6×2 table
     t      y  
    ___    ____

      0    0.82
    0.3    0.72
    0.8    0.63
    1.1     0.6
    1.6    0.55
    2.3     0.5

Попытайтесь моделировать данные с затухающей показательной функцией

y(t)=c1+c2e-t.

Предыдущее уравнение говорит что векторный y должен быть аппроксимирован линейной комбинацией двух других векторов. Каждый - постоянный вектор, содержащий все единицы, и другой вектор с компонентами exp(-t). Неизвестные коэффициенты, c1 и c2, может быть вычислен путем выполнения метода наименьших квадратов, который минимизирует сумму квадратов отклонений данных из модели. Существует шесть уравнений в двух неизвестных, представленных 6 2 матрица.

E = [ones(size(t)) exp(-t)]
E = 6×2

    1.0000    1.0000
    1.0000    0.7408
    1.0000    0.4493
    1.0000    0.3329
    1.0000    0.2019
    1.0000    0.1003

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

c = E\y
c = 2×1

    0.4760
    0.3413

Другими словами, метод наименьших квадратов к данным

y(t)=0.4760+0.3413e-t.

Следующие операторы оценивают модель в расположенном с равными интервалами шаге в t, и затем постройте результат вместе с исходными данными:

T = (0:0.1:2.5)';
Y = [ones(size(T)) exp(-T)]*c;
plot(T,Y,'-',t,y,'o')

E*c не точно равно y, но различие может хорошо быть меньше погрешностей измерения в исходных данных.

Прямоугольный матричный A имеет неполный ранг, если это не имеет линейно независимых столбцов. Если A имеет неполный ранг, затем решение методом наименьших квадратов к AX = B не уникально. A\B выдает предупреждение если A имеет неполный ранг и производит решение методом наименьших квадратов. Можно использовать lsqminnorm найти решение X это имеет минимальную норму среди всех решений.

Недоопределенные системы

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

Вот небольшой, случайный пример:

R = [6 8 7 3; 3 5 4 1]
rng(0);
b = randi(8,2,1)
R =

       6              8              7              3       
       3              5              4              1       


b =

       7       
       8      

Линейная система Rp = b вовлекает два уравнения в четыре неизвестные. Поскольку матрица коэффициентов содержит маленькие целые числа, уместно использовать format команда, чтобы отобразить решение в рациональном формате. Конкретное решение получено с

format rat
p = R\b
p =

       0       
      17/7     
       0       
     -29/7    

Одним из ненулевых компонентов является p(2) потому что R(:,2) столбец R с самой большой нормой. Другим ненулевым компонентом является p(4) потому что R(:,4) доминирует после R(:,2) устраняется.

Полное общее решение недоопределенной системы может быть охарактеризовано путем добавления p к произвольной линейной комбинации пустых векторов пробела, которые могут быть найдены с помощью null функция с опцией, запрашивающей рациональное основание.

Z = null(R,'r')
Z =

      -1/2           -7/6     
      -1/2            1/2     
       1              0       
       0              1       

Это может быть подтверждено тот R*Z нуль и что остаточный R*x - b мал для любого векторного x, где

x = p + Z*q

Начиная со столбцов Z пустые векторы пробела, продукт Z*q линейная комбинация тех векторов:

Zq=(x1x2)(uw)=ux1+wx2.

Чтобы проиллюстрировать, выберите произвольный q и создайте x.

q = [-2; 1];
x = p + Z*q;

Вычислите норму невязки.

format short
norm(R*x - b)
ans =

   2.6645e-15

Когда бесконечно много решений доступны, решение с минимальной нормой особенно интересно. Можно использовать lsqminnorm вычислить решение методом наименьших квадратов минимальной нормы. Это решение имеет наименьшее значение для norm(p).

p = lsqminnorm(R,b)
p =

    -207/137   
     365/137   
      79/137   
    -424/137  

Решение для нескольких правых сторон

Некоторые проблемы касаются решения линейных систем, которые имеют ту же матрицу коэффициентов A, но различные правые стороны b. Когда различные значения b доступны одновременно, можно создать b как матрица с несколькими столбцами и решают все системы уравнений одновременно с помощью одной команды обратной косой черты: X = A\[b1 b2 b3 …].

Однако иногда различные значения b не все доступны одновременно, что означает, что необходимо решить несколько систем уравнений последовательно. Когда вы решаете одну из этих систем уравнений с помощью наклонной черты (/) или обратная косая черта (\), оператор разлагает на множители матрицу коэффициентов A и использование это матричное разложение, чтобы вычислить решение. Однако в каждый последующий раз вы решаете аналогичную систему уравнений с различным b, оператор вычисляет то же разложение A, который является избыточным расчетом.

Решение этой проблемы состоит в том, чтобы предварительно вычислить разложение A, и затем снова используйте факторы, чтобы решить для различных значений b. На практике, однако, предварительное вычисление разложения этим способом может затруднить, поскольку необходимо знать, какое разложение вычислить (LU, LDL, Холесский, и так далее), а также как умножить факторы, чтобы решить задачу. Например, с LU-разложением необходимо решить две линейных системы, чтобы решить исходную систему Ax = b:

[L,U] = lu(A);
x = U \ (L \ b);

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

dA = decomposition(A,'lu');
x = dA\b;

Если вы не уверены который разложение использовать, decomposition(A) выбирает правильный тип на основе свойств A, похожий на то, что делает обратная косая черта.

Вот простой тест возможных выигрышей в производительности этого подхода. Тест решает ту же разреженную линейную систему 100 раз с помощью и обратной косой черты (\) и decomposition.

n = 1e3;
A = sprand(n,n,0.2) + speye(n);
b = ones(n,1);

% Backslash solution
tic
for k = 1:100
    x = A\b;
end
toc
Elapsed time is 9.006156 seconds.
% decomposition solution
tic
dA = decomposition(A);
for k = 1:100
    x = dA\b;
end
toc
Elapsed time is 0.374347 seconds.

Для этой проблемы, decomposition решение намного быстрее, чем использование одной только обратной косой черты, все же синтаксис остается простым.

Итеративные методы

Если матрица коэффициентов A является большой и разреженной, методы факторизации обычно не эффективны. Iterative methods генерирует серию приближенных решений. MATLAB обеспечивает несколько итерационных методов, чтобы обработать большие, разреженные входные матрицы.

ФункцияОписание
pcg

Предобусловленный метод сопряженных градиентов. Этот метод подходит для Эрмитовой положительной определенной матрицы коэффициентов A.

bicg

Метод градиентов BiConjugate

bicgstab

Градиенты BiConjugate стабилизированный метод

bicgstabl

BiCGStab (l) метод

cgs

Методы сопряженных градиентов придали методу квадратную форму

gmres

Обобщенный метод минимальных невязок

lsqr

Метод LSQR

minres

Метод минимальных невязок. Этот метод подходит для Эрмитовой матрицы коэффициентов A.

qmr

Метод квази-минимальных невязок

symmlq

Симметричный метод LQ

tfqmr

Метод QMR без транспонирования

Многопоточное вычисление

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

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

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

  3. Операция не ограничена памятью; время вычислений не во власти времени доступа к памяти. Как правило сложные функции ускоряют больше, чем простые функции.

inv, lscov, linsolve, и mldivide покажите значительное увеличение скорости на больших массивах с двойной точностью (на порядке 10 000 элементов или больше), когда многопоточность будет включена.

Смотрите также

| | | |

Похожие темы