روش ژاکوبی

در جبر خطی عددی ، روش Jacobi یک الگوریتم تکراری برای تعیین راه حل های یک سیستم کاملاً مورب غالب از معادلات خطی است . هر عنصر مورب حل شده است و یک مقدار تقریبی به آن وصل می شود. فرآیند تا زمانی که همگرا شود تکرار می شود. این الگوریتم یک نسخه سلب شده از روش تبدیل جاکوبی از مورب مورباسیون است . این روش به نام کارل گوستاو ژاکوب ژاکوبی نامگذاری شده است .

فهرست

توضیحات [ ویرایش ]

اجازه دهید

$A \ mathbf {x} = \ mathbf {b$

یک سیستم مربع از معادلات خطی n ، که در آن:

$A = {\ fill bmatrix} a_ {11} & a_ {12} & \ cdots & a_ {1n} \\ a_ {21} & a_ {22} & \ cdots & a_ {2n \\\ vdots & \ vdots & \ ddots & \ vdots \\ a_ {n1} & a_ {n2} & \ cdots & a_ {nn \ end {bmatrix}}، \ qquad \ mathbf {x} = {\ fill bmatrix} x_ {1} \\ x_ {2 } \\\ vdots \\ x_ {n} \ end {bmatrix}}، \ qquad \ mathbf {b} = {\ fill bmatrix} b_ {1 \\ b_ {2} \\\ vdots \\ b_ { n} \ end {bmatrix.$

سپس را می توان به تجزیه مورب جزء D ، یک قسمت پایین مثلثی L و بخش مثلثی بالای U :

$\ displaystyle A = D + L + U \ qquad {\ text {جایی که}} \ qquad D = {\ fill {bmatrix} a_ {11} & 0 & \ cdots & 0 \\ 0 & a_ {22} & \ cdots & 0 \\\ vdots & \ vdots & \ ddots & \ vdots \\ 0 & 0 & \ cdots & a_ {nn} \ end {bmatrix}} {\ text {و} + L + U = {\ شروع {bmatrix 0 & a_ {12} & \ cdots & a_ {1n} \\ a_ {21} & 0 & cdots & a_ {2n} \\\ vdots & \ vdots & \ dots & \ vdots \\ a_ {n1} & a_ {n2} & \ cdots & 0 \ end {bmatrix}. }$

سپس محلول به صورت تکراری از طریق بدست می آید

$\ displaystyle \ mathbf {x} ^ {(k + 1)} = D ^ {- 1} (\ mathbf {b} - (L + U) \ mathbf {x} ^ {(k)})،}$

جایی که $\ mathbf {x} ^ {(k)$ است ک هفتم تقریب و یا تکرا $\ mathbf {x$ و $\ mathbf {x} ^ {(k + 1)$ تکرار بعدی یا k + 1 است $\ mathbf {x$ . فرمول مبتنی بر عنصر بدین ترتیب است:

$x_ {i} ^ {(k + 1)} = {\ frac {1} {a_ {ii}}} \ سمت چپ (b_ {i} - \ sum _ {j \ neq i} a_ {ij} x_ {j } ^ {(k) right \ درست) ، \ quad i = 1،2 ، \ ldots ، n.$

محاسبه $\ displaystyle x_ {i} ^ {(k + 1)}}$ نیاز به هر عنصر در x ( k ) به جز خود دارد. برخلاف روش گاوس-سییدل ، ما نمی توانیم بازنویسی کنیم $\ displaystyle x_ {i} ^ {(k)$ با $\ displaystyle x_ {i} ^ {(k + 1)}}$ ، زیرا این مقدار توسط بقیه محاسبات مورد نیاز خواهد بود. حداقل مقدار ذخیره سازی دو بردار اندازه n است .

الگوریتم [ ویرایش ]

ورودی:  حدس اولیهبه محلول ، (مورب غالب مورب)
  
      
، وکتور سمت راست   
، معیار همگرایی
 خروجی:  راه حل هنگامی که همگرایی حاصل شد 
نظرات:  شبه کد بر اساس فرمول مبتنی بر عنصر فوق


در حالی که همگرایی رسیده است انجام 
    برای من: = 1 مرحله تا N انجام

        برای j: = 1 مرحله تا زمانی که n do انجام دهم 
            اگر j ≠ i باشد

            پایان 
        پایان

    پایان

پایان

همگرایی [ ویرایش ]

شرط همگرایی استاندارد (برای هر روش تکراری) زمانی است که شعاع طیفی ماتریس تکرار کمتر از 1 باشد:

$\ displaystyle \ rho (D ^ {- 1} (L + U)) <1.$

شرط کافی (اما لازم نیست) برای همگرایی روش این است که ماتریس A کاملاً یا غیرقابل برگشت به صورت مورب مسلط است . تسلط مورب سخت گیرانه به این معنی است که برای هر سطر ، مقدار مطلق اصطلاح مورب از مجموع مقادیر مطلق سایر اصطلاحات بیشتر است:

$\ سمت چپ | a_ {ii} \ Right |> \ sum _ {j \ neq i} {\ left | a_ {ij} \ Right |.$

روش ژاکوبی حتی اگر این شرایط راضی نباشد گاهی همگرا می شود.

توجه داشته باشید که روش Jacobi برای هر ماتریس مثبت مثبت متقارن همگرا نیست . مثلا

$\ displaystyle A = {\ fill {pmatrix} 29 & 2 & 1 \\ 2 & 6 & 1 \\ 1 & 1 & {\ frac {1} {5}} \ end {pmatrix}} \ quad \ Rightarrow \ quad D ^ {- 1} (L + U ) = {\ fill pmatrix} 0 & {\ frac {2} 29}} & {\ frac {1 {29}} \\ {\ frac {1} {3}} & 0 & {\ frac {1} 6}} \\ 5 & 5 & 0 \ end {pmatrix} \ quad \ Rightarrow \ quad \ rho (D ^ {- 1} (L + U)) \ تقریبا 1.0661 \ ،.}$

مثال [ ویرایش ]

یک سیستم خطی از فرم $تبر = ب$ با برآورد اولیه $x ^ {{(0)}}$ از رابطه زیر بدست می آید

$A = {\ fill bmatrix} 2 & 1 \\ 5 & 7 \\ end {bmatrix}}، \ b = {\ fill bmatrix} 11 \\ 13 \* end {bmatrix} \ quad {\ متن {و} } \ quad x ^ {(0) = {\ fill bmatrix} 1 \\ 1 \\\ end {bmatrix.$

ما از معادله استفاده می کنیم $\ displaystyle x ^ {(k + 1)} = D ^ {- 1} (b- (L + U) x ^ {(k)})$ ، در بالا شرح داده شده ، برای برآورد $ایکس$ . ابتدا معادله را به روشی راحت تر بازنویسی می کنیم $\ displaystyle D ^ {- 1} (b- (L + U) x ^ {(k)}) = Tx ^ {(k) + C$ ، جایی که $\ displaystyle T = -D ^ {- 1} (L + U)$ و $C = D ^ {- 1} b$ . از مقادیر شناخته شده

$D ^ {- 1} = {\ fill {bmatrix} 1/2 & 0 \\ 0 & 1/7 \\ end end {bmatrix}}، \ L = {\ fill bmatrix 0 & 0 \\ 5 & 0 \\ end end {bmatrix } \ quad {\ text و}} \ quad U = begin \ آغاز {bmatrix} 0 & 1 \\ 0 & 0 \\ end {bmatrix}.$

ما تعیین می کنیم $T = -D ^ {- 1} (L + U)$ مانند

$T = {\ fill bmatrix} 1/2 & 0 \\ 0 & 1/7 \\\ end {bmatrix}} \ left \ {begin \ fill {bmatrix 0 & 0 \\ - 5 & 0 \ end end {bmatrix}} + {\ fill bmatrix} 0 & -1 \\ 0 & 0 \\\ end {bmatrix} \ Right \} = {\ fill bmatrix 0 & -1 / 2 \\ - 5/7 & 0 \\\ end {bmatrix}.$

به علاوه، $ج$ به عنوان یافت می شود

$C = {\ fill bmatrix} 1/2 & 0 \\ 0 & 1/7 \\\ end {bmatrix}} {\ fill bmatrix} 11 \\ 13 \\ end end {bmatrix} = {\ fill {bmatrix 11 / 2 \\ 13/7 \\\ end {bmatrix.$

با $تی$ و $ج$ محاسبه شده ، ما تخمین می زنیم $ایکس$ مانند $x ^ {(1) = Tx ^ {(0)} + C$ :

$x ^ {(1) = {\ آغاز {bmatrix} 0 & -1 / 2 \\ - 5/7 & 0 \\\ end {bmatrix}} {\ fill bmatrix 1 \\ 1 \\ end {bmatrix } + {\ fill bmatrix} 11/2 \\ 13/7 \\ end end {bmatrix}} = {\ fill {bmatrix} 5.0 \\ 8/7 \** end {bmatrix} \ تقریبی {\ آغاز bmatrix} 5 \\ 1.143 \\* end {bmatrix}.$

تکرار بعدی بازده است

$x ^ {(2) = {\ fill bmatrix} 0 & -1 / 2 \\ - 5/7 & 0 \\\ end {bmatrix}} {\ fill bmatrix} 5.0 \\ 8/7 \\ end end bmatrix}} + {\ fill bmatrix} 11/2 \\ 13/7 \\\ end {bmatrix}} = {\ fill bmatrix 69/14 \ - - 12/7 \\ end end {bmatrix \ تقریبی {\ آغاز {bmatrix 9 4.929 \ - 1.714 \\\ end {bmatrix}.$

این روند تا همگرایی تکرار می شود (یعنی تا زمانی که $\ | تبر ^ {(ن) - b \ |$ کوچک است) راه حل پس از 25 تکرار است

$x = {\ fill bmatrix} 7.111 \\ - 3.222 \ end {bmatrix.$

مثال دیگر [ ویرایش ]

فرض کنید سیستم خطی زیر به ما داده می شود:

${\ شروع {تراز شده} 10x_ {1} -x_ {2} + 2x_ {3} & = 6، \\ - x_ {1} + 11x_ {2} -x_ {3} + 3x_ {4} & = 25، \\ 2x_ {1} -x_ {2} + 10x_ {3} -x_ {4} & = - 11، \\ 3x_ {2} -x_ {3} + 8x_ 4} & = 15. \ end {تراز شده }$

اگر (0 ، 0 ، 0 ، 0) را به عنوان تقریب اولیه انتخاب کنیم ، سپس اولین راه حل تقریبی توسط

$\ displaystyle {\ شروع {تراز شده} x_ {1} & = (6 + 0- (2 * 0)) / 10 = 0.6 ، \\ x_ {2} & = (25 + 0 + 0- (3 * 0 )) / 11 = 25/11 = 2.2727 ، \\ x_ {3} & = (- 11- (2 * 0) + 0 + 0) /10=-1.1 ، \\ x_ {4} & = (15- (3 * 0) +0) /8=1.875.*end {تراز شده}}}$

با استفاده از تقریبهای به دست آمده ، روش تکراری تا رسیدن به دقت مطلوب تکرار می شود. در زیر راه حل های تقریبی بعد از پنج تکرار است.

$x_ {1$	$x_ {2$	$x_ {3$	$x_ {4$
0.6	2.27272	-1.1	1.875
1.04727	1.7159	-0.80522	0.88522
0.93263	2.05330	-1.0493	1.13088
1.01519	1.95369	-0.9681	0.97384
0.98899	2.0114	-1.0102	1.02135

راه حل دقیق سیستم (1 ، 2 ، −1 ، 1) است .

مثالی با استفاده از پایتون و نامپی [ ویرایش ]

روش عددی زیر به سادگی برای تولید بردار راه حل تکرار می کند.

def jacobi(A, b, x_init, epsilon=1e-10, max_iterations=500):
    D = np.diag(np.diag(A))
    LU = A - D
    x = x_init
    for i in range(max_iterations):
        D_inv = np.diag(1 / np.diag(D))
        x_new = np.dot(D_inv, b - np.dot(LU, x))
        if np.linalg.norm(x_new - x) < epsilon:
            return x_new
        x = x_new
    return x

# problem data
A = np.array([
    [5, 2, 1, 1],
    [2, 6, 2, 1],
    [1, 2, 7, 1],
    [1, 1, 2, 8]
])
b = np.array([29, 31, 26, 19])

# you can choose any starting vector
x_init = np.zeros(len(b))
x = jacobi(A, b, x_init)

print('x:', x)
print('computed b:', np.dot(A, x))
print('real b:', b)

Produces the output:

x: [3.99275362 2.95410628 2.16183575 0.96618357]
computed b: [29. 31. 26. 19.]
real b: [29 31 26 19]

روش ژاکوبی وزنی [ ویرایش ]

تکرار وزنی ژاکوبی از یک پارامتر استفاده می کند $\ امگا$ برای محاسبه تکرار به عنوان

$\ displaystyle \ mathbf {x} ^ {(k + 1)} = \ omega D ^ {- 1} (\ mathbf {b} - (L + U) \ mathbf {x} ^ {(k)}) + \ سمت چپ (1- \ امگا \ راست) \ mathbf {x} ^ {(k)}$

با $\ امگا = 2/3$ انتخاب معمول بودن [1]

همگرایی در مورد قطعی مثبت متقارن [ ویرایش ]

در صورتی که ماتریس سیستم $آ$ از نوع متقارن مثبت است که می تواند همگرایی را نشان دهد.

اجازه دهید $\ displaystyle C = C _ {\ omega} = I- \ omega D ^ {- 1} A}$ ماتریس تکرار باشد. سپس ، همگرایی برای آن تضمین شده است

$\ displaystyle \ rho (C _ {\ omega) <1 \ quad \ Longleftrightarrow \ quad 0 <\ omega <{\ frac {2} {\ lambda _ {\ text {max}} (D ^ {- 1} A )}} \،$

جایی که $\ displaystyle \ lambda _ {\ text {حداکثر}}}$ حداکثر ارزش ویژه است.

شعاع طیفی را می توان برای انتخاب خاص از به حداقل رساند $\ displaystyle \ omega = \ omega _ {\ text {opt}}$ به شرح زیر است

$\ displaystyle \ min _ {\ omega} \ rho (C _ {\ omega) = \ rho (C _ {\ omega _ {\ text {opt}}}) = 1 - {\ frac {2} {\ kappa ( D ^ {- 1} A) +1}} \ quad {\ text {برای}} \ quad \ omega _ {\ متن {opt}}: = {\ frac {2} {\ lambda _ {\ text {min } (D ^ {- 1} A) + \ lambda _ {\ text {max}} (D ^ {- 1} A)}} \ ،،}$

جایی که (kappa) $\ کاپا$ است تعداد شرط ماتریس .

منبع

https://en.wikipedia.org/wiki/Jacobi_method

+ نوشته شده در دوشنبه سی ام تیر ۱۳۹۹ ساعت 14:10 توسط علی رضا نقش نیلچی |

ریاضیات

آموزش ریاضی

روش ژاکوبی

فهرست

توضیحات [ ویرایش ]

الگوریتم [ ویرایش ]

همگرایی [ ویرایش ]

مثال [ ویرایش ]

مثال دیگر [ ویرایش ]

مثالی با استفاده از پایتون و نامپی [ ویرایش ]

روش ژاکوبی وزنی [ ویرایش ]

همگرایی در مورد قطعی مثبت متقارن [ ویرایش ]

پیوندهای روزانه

نوشته‌های پیشین

آرشیو موضوعی

پیوندها

آمارگیر وبلاگ

کد پربازدیدترین