AlgoVerse

حل دستگاه معادلات خطی

A·x = b را با تجزیه‌ی LUP و دو جای‌گذاری حل می‌کند: اول L·y = P·b رو به جلو، بعد U·x = y رو به عقب؛ با کسرهای دقیق.

با تجزیه‌ی P·A = L·U، معادله‌ی A·x = b دو معادله‌ی مثلثی می‌شود:

ادامه‌ی توضیح ↓
ورودی:
A 3×3 · b 3×1خروجی PDF

A = [[1, 2, 0], [3, 4, 4], [5, 6, 3]] و b = (3, 7, 8)؛ جواب x = (−7/5، 11/5، 3/5).

  1. from fractions import Fraction
  4. def solve(A, b):
  5. n = len(A)
  6. if len(b) != n:
  7. return None
  8. a = [[Fraction(x) for x in row] for row in A]
  9. pi = list(range(n))
  10. # 1. P·A = L·U (as on the LUP decomposition page).
  11. for k in range(n):
  12. p = max(range(k, n), key=lambda i: abs(a[i][k]))
  13. if a[p][k] == 0:
  14. return None
  15. pi[k], pi[p] = pi[p], pi[k]
  16. a[k], a[p] = a[p], a[k]
  17. for i in range(k + 1, n):
  18. a[i][k] = a[i][k] / a[k][k]
  19. for j in range(k + 1, n):
  20. a[i][j] = a[i][j] - a[i][k] * a[k][j]
  21. lu = a
  22. # 2. Forward substitution: L·y = P·b.
  23. y = [Fraction(0)] * n
  24. for i in range(n):
  25. y[i] = b[pi[i]][0] - sum(lu[i][j] * y[j] for j in range(i))
  26. # 3. Back substitution: U·x = y.
  27. x = [Fraction(0)] * n
  28. for i in range(n - 1, -1, -1):
  29. x[i] = (y[i] - sum(lu[i][j] * x[j] for j in range(i + 1, n))) / lu[i][i]
  30. return [str(v) for v in x]

ناوردا: در جای‌گذاری رو به عقب، x[i+1] تا x[n−1] از قبل معلوم‌اند، پس معادله‌ی سطر i فقط یک مجهول دارد.

شروع اجرا

pi—
y—
x—

جدول هنوز خالی است.

متغیرهای محلی

نارنجی = در همین گام عوض شد

A list

[1, 2, 0][3, 4, 4][5, 6, 3]

b list

[3][7][8]

Call stack

  1. solve()خط 4
گام ۱ از ۶۱
خط سیاه = backward · خط نارنجی = گام کلیدیfactored: 0/1 · forward: 0/3 · backward: 0/3
    توضیح

    ایده

    با تجزیه‌ی P·A = L·U، معادله‌ی A·x = b دو معادله‌ی مثلثی می‌شود:

    1. L·y = P·b: چون L پایین‌مثلثی است، y[0] مستقیم معلوم است، بعد y[1] و … (جای‌گذاری رو به جلو).
    2. U·x = y: چون U بالامثلثی است، از آخرین سطر شروع می‌کنیم: x[n−1] و بعد بالاتر (جای‌گذاری رو به عقب).

    هزینه

    تجزیه O(n³) است، ولی هر جای‌گذاری فقط O(n²). برای چند b مختلف با همان A، فقط یک بار تجزیه می‌کنیم. (حساب کردن A⁻¹ و ضرب در b کندتر و از نظر عددی بدتر است.)

    در trace به چه چیزی نگاه کنی

    • جدول lu همان L و U در یک ماتریس است؛ کارت‌های y و x به ترتیب از بالا به پایین و از پایین به بالا پر می‌شوند.