• Author / Uploaded
• One Piece

Citation preview

1. Use Gaussian elimination with backward substitution and two-digit rounding arithmetic to solve the following linear systems. Do not reorder the equations. (The exact solution to each system is 𝑥1 = −1, 𝑥2 = 1, 𝑥3 = 3). −𝑥1 + 4𝑥2 + 𝑥3 = 8 5 2 2 𝑥1 + 𝑥2 + 𝑥3 = 1 3 3 3 2𝑥1 + 𝑥2 + 4𝑥3 = 11

[Exerciser set 6.1 page368, 4(a)] Solution: Converting given equations into matrix form −1

4

[1.67

0.67

2

1

1

8

0.67| 1 ] 4

11

𝑅2 ← 𝑅2 + 1.67 × 𝑅1 −1 [0 2

4

1

7.35 1

8

2.34|14.36] 4

11

𝑅3 ← 𝑅3 + 2 × 𝑅1 −1 [0 0

4 7.35 9

𝑅3 ← 𝑅3 − −1 [0 0

1

2.34|14.36] 6

27

9 × 𝑅2 7.35

4 7.35 0

8

1

8

2.34|14.36] 3.13 9.42

So, −𝑥1 + 4𝑥2 + 𝑥3 = 8 … … … … … … . . . (𝑖) 7.35𝑥2 + 2.34𝑥3 = 14.36 … … … … … … … … (𝑖𝑖) 3.13𝑥3 = 9.42 … … … … … … … … … … … (𝑖𝑖𝑖)

1

Now use the backward substitution method: 𝐹𝑟𝑜𝑚 (𝑖𝑖𝑖) 𝑥3 = 3.01

𝐹𝑟𝑜𝑚 (𝑖𝑖) 7.35𝑥2 + 2.34 × 3.01 = 14.36 ⇒ 7.35𝑥2 = 7.32 ⇒ 𝑥2 = 1

𝐹𝑟𝑜𝑚 (𝑖) −𝑥1 + 4 × 1 + 3.01 = 8 ⇒ 𝑥1 = −0.99

So, 𝑥1 = −0.99, 𝑥2 = 1, 𝑥3 = 3.01 2. Use Gaussian elimination and three-digit chopping arithmetic to solve the following linear systems, and compare the approximations to the actual solution. 3.03𝑥1 − 12.1𝑥2 + 14𝑥3 = −119 −3.03𝑥1 + 12.1𝑥2 − 7𝑥3 = 120 6.11𝑥1 − 14.2𝑥2 + 21𝑥3 = −139 1 𝐴𝑐𝑡𝑢𝑎𝑙 𝑆𝑜𝑙𝑢𝑡𝑖𝑜𝑛 [0,10, ] 7

[Exerciser set 6.2 page 380, 9(b)] Solution: Converting given equations into matrix form 3.03

−12.1

14 −119

[−3.03

12.1

−7| 120 ]

6.11

−14.2

21 −139

𝑅2 ← 𝑅2 + 𝑅1 3.03

−12.1

[ 0 6.11

0 −14.2

𝑅3 ← 𝑅3 −

14 −119 7| 1 ] 21 −139

611 × 𝑅1 303

2

3.03

−12.1

14

0

7

[ 0 0

10.2

−119 |

1

]

−7.231 100.964

𝐴𝑓𝑡𝑒𝑟 𝑖𝑛𝑡𝑒𝑟𝑐ℎ𝑎𝑛𝑔𝑖𝑛𝑔 𝑟𝑜𝑤𝑠 𝑅2 ↔ 𝑅3 3.03

−12.1

[ 0

10.2

0

14

−119

−7.231|100.964]

0

7

1

So, 3.03𝑥1 − 12.1𝑥2 + 14𝑥3 = −119 … … … … … … . . . (𝑖) 10.2𝑥2 − 7.2314𝑥3 = 100.964 … … … … … … … … (𝑖𝑖) 7𝑥3 = 1 … … … … … … … … … … … (𝑖𝑖𝑖)

Now use the backward substitution method: 𝐹𝑟𝑜𝑚 (𝑖𝑖𝑖) 𝑥3 = 0.143

𝐹𝑟𝑜𝑚 (𝑖𝑖) 10.2𝑥2 − 7.231 × 0.143 = 100.964 ⇒ 10.2𝑥2 = 101.998 ⇒ 𝑥2 = 10

𝐹𝑟𝑜𝑚 (𝑖) 3.03𝑥1 − 12.1 × 10 + 14 × 0.143 = −119 ⇒ 𝑥1 = 0

So, 𝑥1 = 0, 𝑥2 = 10, 𝑥3 = 0.143 3. Factor the following matrices into the LU decomposition using the LU Factorization Algorithm with 𝑙𝑖𝑖 = 1 for all i. 2 −1 1 [3 3 9 ] 3 3 5 [Exerciser set 6.5 page 410, 5(a)] Solution: Here, 3

2 −1 1 [3 3 9 ] 3 3 5 𝑅2 ← 𝑅2 − 1.5 × 𝑅1 [⸫ 𝐿2,1 = 1.5] 2 −1 1 [0 4.5 7.5] 3 3 5 𝑅3 ← 𝑅3 − 1.5 × 𝑅1 [⸫ 𝐿3,1 = 1.5] 2 −1 1 [0 4.5 7.5] 0 4.5 3.5 𝑅3 ← 𝑅3 − 1 × 𝑅2 [⸫ 𝐿3,2 = 1] 2 −1 1 [0 4.5 7.5] 0 0 −4 2 −1 1 ⸫ 𝑈 = [0 4.5 7.5] 0 0 −4 1 0 0 ⸫ 𝐿 = [1.5 1 0] 1.5 1 1 So, LU decomposition is 2 −1 1 1 0 0 2 [3 3 9] = [1.5 1 0] × [0 3 3 5 1.5 1 1 0

−1 1 4.5 7.5] = 𝐿𝑈 0 −4

4. Obtain factorizations of the form 𝐴 = 𝑃𝑡 𝐿𝑈 for the following matrices. 0 𝐴 = [1 0

2 3 1 −1] −1 1

[Exerciser set 6.5 page 411, 9(a)] Solution: 0 2 3 [1 1 −1] 0 −1 1 𝑅1 ↔ 𝑅2

4

1 1 −1 [0 2 3] 0 −1 1 1 1 𝑅3 ← 𝑅3 − (− ) × 𝑅2 [⸫ 𝐿3,2 = − ] 2 2 1 0 [ 0

1 −1 2 3 5] 0 2

1 0 ⸫𝑈 =[ 0

1 −1 2 3 5] 0 2

The permutation matrix associated with the row interchanges 𝑅1 ↔ 𝑅2 0 1 0 ⸫ 𝑃 = [1 0 0 ] 0 0 1 0 1 0 ⸫ 𝑃−1 = 𝑃𝑇 = [1 0 0] 0 0 1 1 0

0 1 ⸫𝐿 =[ 1 0 − 2 0 ⸫ 𝑃𝑇 𝐿𝑈 = [1 0

0 0 ] 1 1 1 0 0 0 0] [ 0 1 0

0 0 1 1 −1 1 0 0 2 3 ][ 1 5] − 1 0 0 2 2

5. Use the Cholesky Algorithm to find a factorization of the form 𝐴 = 𝐿𝐿𝑡 for the matrices 4 𝐴 = [−1 1

−1 1 3 0] 0 2

Solution: 4 𝐴 = [−1 1

−1 1 3 0] 0 2

5

6

⸫

𝑆𝑜, 𝐴 = 𝐿𝐿𝑡 =

×

6. Use Crout factorization for tridiagonal systems to solve the following linear systems.

[Exerciser set 6.6 page 426, 12(d)] Solution: 2𝑥1 − 𝑥2 + 0𝑥3 + 0𝑥4 + 0𝑥5 = 1 … … … … … (𝑖) 𝑥1 + 2𝑥2 − 𝑥3 + 0𝑥4 + 0𝑥5 = 2 … … … … … (𝑖𝑖) 0𝑥1 + 2𝑥2 + 4𝑥3 − 𝑥4 + 0𝑥5 = −1 … … … … … (𝑖𝑖𝑖) 0𝑥1 + 0𝑥2 + 0𝑥3 + 2𝑥4 − 𝑥5 = −2 … … … … … (𝑖𝑣) 0𝑥1 + 0𝑥2 + 0𝑥3 + 𝑥4 + 2𝑥5 = −1 … … … … … (𝑣) Now converting the given matrix equations into matrix form

7

𝑥1 0 0 1 𝑥2 0 0 2 𝑥 −1 0 3 = −1 2 −1 𝑥4 −2 ] [ 𝑥 ] [ 1 2 5 −1]

2 −1 0 1 2 −1 0 2 4 0 0 0 [0 0 0 Now,

𝑥1 2 −1 0 0 0 1 𝑥 2 1 2 −1 0 0 2 𝐴= 0 2 4 −1 0 𝑥 = 𝑥3 and 𝐵 = −1 𝑥4 0 0 0 2 −1 −2 [0 0 [𝑥5 ] [−1] 0 1 2] Here, 2 −1 0 0 0 1 2 −1 0 0 𝐴= 0 2 4 −1 0 0 0 0 2 −1 [0 0 0 1 2] 1 1 𝑅2 ← 𝑅2 − × 𝑅1 [⸫ 𝐿2,1 = ] 2 2 2

−1

0

0

0

0

5 2

−1

0

0

0

2

4

−1

0

0

0

0

2

−1

[0

0

0

1

2]

4 4 𝑅3 ← 𝑅3 − × 𝑅2 [⸫ 𝐿3,2 = ] 5 5 2

−1

0

0

0

0

5 2

−1

0

0

0

0

24 5

−1

0

0

0

0

2

−1

[0

0

0

1

2]

1 1 𝑅5 ← 𝑅5 − × 𝑅4 [⸫ 𝐿5,4 = ] 2 2

8

2

−1

0

0

0

0

5 2

−1

0

0

0

0

24 5

−1

0

0

0

0

2

−1

[0

0

0

0

5 2]

2

−1

0

0

0

1

0

0

0

0

0

5 2

−1

0

0

1

0

0

0

⸫𝑈 = 0

0

24 5

1 2

−1

0

𝑎𝑛𝑑 𝐿 = 0

4 5

1

0

0

0

0

0

2

−1

0

0

0

1

0

[0

0

0

0

[0

0

0

1 2

1]

5 2]

⸫ LU decomposition for A is: 1 1 2 −1 0 0 0 2 1 2 −1 0 0 𝐴= 0 2 4 −1 0 = 0 0 0 0 2 −1 0 [0 0 0 1 2] [0

0

0

0

0

2

−1

0

0

0

1

0

0

0

0

−1

0

0

4 5

5 2

1

0

0 × 0

0

24 5

−1

0

0

0

1

0

0

0

0

2

−1

0

0

1 2

1]

[0

0

0

0

5 2]

𝑁𝑜𝑤, 𝐴𝑥 = 𝐵, 𝑎𝑛𝑑 𝐴 = 𝐿𝑈 ⇒ 𝐿𝑈𝑥 = 𝐵 𝑙𝑒𝑡, 𝑈𝑥 = 𝑦, 𝑡ℎ𝑒𝑛 𝐿𝑦 = 𝐵 ⇒ 1

0

0

0

0

𝑦1

1

1 2

1

0

0

0

𝑦2

2

0

4 5

1

0

0 × 𝑦3 = −1

0

0

0

1

0

𝑦4

−2

0

1 2

1]

[𝑦5 ]

[−1]

[0

0

𝑦1 = 1 … … … … … (𝑣𝑖)

9

1 𝑦 + 𝑦2 = 2 … … … … … (𝑣𝑖𝑖) 2 1 4 𝑦 + 𝑦3 = −1 … … … … … (𝑣𝑖𝑖𝑖) 5 2 𝑦4 = −2 … … … … … (𝑖𝑥) 1 𝑦 + 𝑦5 = −1 … … … … … (𝑥) 2 4 𝐹𝑟𝑜𝑚 𝑒𝑞𝑢𝑎𝑡𝑖𝑜𝑛 (𝑣𝑖𝑖) 1 3 × 1 + 𝑦2 = 2 ⇒ 𝑦2 = 2 2 𝐹𝑟𝑜𝑚 𝑒𝑞𝑢𝑎𝑡𝑖𝑜𝑛 (𝑣𝑖𝑖𝑖) 4 3 11 × + 𝑦3 = −1 ⇒ 𝑦3 = − 5 2 5 𝐹𝑟𝑜𝑚 𝑒𝑞𝑢𝑎𝑡𝑖𝑜𝑛 (𝑥) 1 × (−2) + 𝑦5 = −1 ⇒ 𝑦5 = 0 2 𝑁𝑜𝑤, 𝑈𝑥 = 𝑦 2

−1

0

0

0

𝑥1

0

5 2

−1

0

0

𝑥2

0

0

24 5

−1

0

0

0

2

[0

0

0

0

0 × 𝑥3 −1 5 2]

1 3 2 11 = − 5

𝑥4

−2

[𝑥5 ]

[ 0 ]

2𝑥1 − 𝑥2 = 1 … … … … … (𝑥𝑖) 5 3 𝑥2 − 𝑥3 = … … … … … (𝑥𝑖𝑖) 2 2 24 11 𝑥3 − 𝑥4 = − … … … … … (𝑥𝑖𝑖𝑖) 5 5 2𝑥4 − 𝑥5 = −2 … … … … … (𝑥𝑖𝑣) 5 𝑥 = 0 … … … … … (𝑥𝑣) 2 5 10

𝐹𝑟𝑜𝑚 (𝑥𝑣) 𝑥5 = 0 𝐹𝑟𝑜𝑚 (𝑥𝑖𝑣) 2𝑥4 − 0 = −2 ⇒ 𝑥4 = −1 𝐹𝑟𝑜𝑚 (𝑥𝑖𝑖𝑖) 24 11 2 𝑥3 − (−1) = − ⇒ 𝑥3 = − 5 5 3 𝐹𝑟𝑜𝑚 (𝑥𝑖𝑖) 5 2 3 1 𝑥2 − (− ) = ⇒ 𝑥2 = 2 3 2 3 𝐹𝑟𝑜𝑚 (𝑥𝑖) 2𝑥1 −

1 2 = 1 ⇒ 𝑥1 = 3 3

Solution by Crout’s method is 𝑥1 =

2 1 2 , 𝑥2 = , 𝑥3 = − , 𝑥4 = −1 , 𝑥5 = 0 3 3 3

11