Q1Easy
Gaussian elimination with partial pivoting (GEPP) for Ax=b: at each step k, swap rows to bring the largest element in column k to the pivot position. The purpose of partial pivoting is:
Ax=b க்கான பகுதி பிவோட்டிங்குடன் (GEPP) காஸியன் நீக்கம்: ஒவ்வொரு அடியிலும் k, நெடுவரிசை k இல் உள்ள பெரிய உறுப்பை பிவோட் நிலைக்கு கொண்டு வர வரிசைகளை மாற்றவும். பகுதி மையப்படுத்தலின் நோக்கம்:
- aTo make A symmetric — ஒரு சமச்சீர் செய்ய
- bTo reduce storage — சேமிப்பைக் குறைக்க
- cTo speed up computation — கணக்கீட்டை விரைவுபடுத்த
- dTo avoid small pivots (which would amplify round-off errors); GEPP reduces the growth factor compared to no pivoting — சிறிய பிவோட்களைத் தவிர்க்க (இது ரவுண்ட்-ஆஃப் பிழைகளை பெருக்கும்); GEPP வளர்ச்சிக் காரணியைக் குறைக்கிறது✓ Correct
Explanation
GEPP: find max|a_{jk}| for j>=k, swap row j and row k, then eliminate. Without pivoting: a_{11}=epsilon (tiny) causes division by epsilon in the first step -- catastrophic amplification. GEPP ensures |a_{kk}| >= |a_{jk}| for all j>k. The growth factor rho = max element after elimination / max before <= 2^{n-1}. In practice rho is modest. Cost: O(n^3) flops with O(n^2) storage.
GEPP: கண்டுபிடி அதிகபட்சம்|a_{jk}| j>=k க்கு, j மற்றும் வரிசை k ஐ மாற்றவும், பின்னர் நீக்கவும். பிவோட்டிங் இல்லாமல்: a_{11}=எப்சிலான் (சிறியது) முதல் படியில் எப்சிலானால் பிரிவை ஏற்படுத்துகிறது -- பேரழிவு பெருக்கம். GEPP உறுதி செய்கிறது |a_{kk}| >= |a_{jk}| அனைவருக்கும் j>k. வளர்ச்சி காரணி rho = நீக்குதலுக்குப் பிறகு அதிகபட்ச உறுப்பு / <= 2^{n-1}க்கு முன் அதிகபட்சம். நடைமுறையில் ரோ சுமாரானது. விலை: O(n^2) சேமிப்பகத்துடன் O(n^3) தோல்வியடைந்தது.
Q2Easy
LU decomposition: A = LU (or PA = LU with pivoting). Once L and U are computed, solving Ax=b for multiple right-hand sides b_1,...,b_k costs:
LU சிதைவு: A = LU (அல்லது PA = LU உடன் பிவோட்டிங்). L மற்றும் U கணக்கிடப்பட்டவுடன், பல வலது பக்கங்களுக்கு Ax=b ஐ தீர்க்கும் b_1,...,b_k செலவுகள்:
- aO(n^3) per right-hand side — வலது பக்கத்திற்கு O(n^3)
- bO(n^2) per right-hand side (forward substitution Ly=b then backward substitution Ux=y), after the one-time O(n^3) LU factorization — ஒரு முறை O(n^3) LU காரணியாக்கத்திற்குப் பிறகு, வலது புறம் ஒன்றுக்கு O(n^2) (முன்னோக்கி மாற்று Ly=b பின்னர் பின்தங்கிய மாற்று Ux=y),✓ Correct
- cO(n^4) total — மொத்தம் O(n^4)
- dO(n) per right-hand side — வலது பக்கத்திற்கு O(n)
Explanation
LU factorization: O(n^3/3) flops (FLOP count: 2n^3/3 for dense). Once PA=LU is computed, each solve Ax=b: (1) Pb=Pb (O(n)), (2) forward substitution Ly=Pb (O(n^2)), (3) backward substitution Ux=y (O(n^2)). Multiple right-hand sides: O(kn^2) total after O(n^3) factorization. Critical for problems like finite element analysis with multiple load cases.
LU காரணியாக்கம்: O(n^3/3) தோல்விகள் (FLOP எண்ணிக்கை: 2 n^3/3 அடர்த்திக்கு). PA=LU கணக்கிடப்பட்டவுடன், ஒவ்வொன்றும் Ax=b: (1) Pb=Pb (O(n)), (2) முன்னோக்கி மாற்றீடு Ly=Pb (O(n^2)), (3) பின்தங்கிய மாற்று Ux=y (O(n^2)) ஐ தீர்க்கும். பல வலது பக்கங்கள்: O(n^2)1 காரணிப்படுத்தலுக்குப் பிறகு மொத்தம் O(n^2)0. பல சுமை வழக்குகளுடன் வரையறுக்கப்பட்ட உறுப்பு பகுப்பாய்வு போன்ற சிக்கல்களுக்கு முக்கியமானது.
Q3Easy
Cholesky decomposition: for a symmetric positive definite (SPD) matrix A, A = L*L^T where L is lower triangular with positive diagonal. Advantages over LU for SPD matrices:
கோலஸ்கி சிதைவு: ஒரு சமச்சீர் நேர்மறை திட்டவட்டமான (SPD) அணி A, A = L* L^T க்கு L ஆனது நேர்மறை மூலைவிட்டத்துடன் கீழ் முக்கோணமாக இருக்கும். SPD மெட்ரிக்குகளுக்கு LU ஐ விட நன்மைகள்:
- aA = Q R (where Q is orthogonal and R is upper triangular) — A = Q R (இங்கு Q செங்குத்து மற்றும் R மேல் முக்கோண அணி)
- bA = U Σ V^T (singular value decomposition for general rectangular matrices) — A = U Σ V^T (செவ்வக அணிகளுக்கான தனித்துவ மதிப்பு சிதைவு)
- cA = L L^T (where L is a lower triangular matrix with positive diagonal entries) — A = L L^T (இங்கு L என்பது நேர்மறை மூலைவிட்ட உறுப்புகள் கொண்ட கீழ் முக்கோண அணி)✓ Correct
- dA = L U with unit diagonal entries on both triangular factors — இரு முக்கோண காரணிகளிலும் அலகு மூலைவிட்ட உறுப்புகளுடன் A = L U
Explanation
Cholesky: exists iff A is SPD. L_{kk}=sqrt(A_{kk} - sum_{j<k} L_{kj}^2). Numerically stable without pivoting (diagonal entries stay positive). Cost: n^3/6 multiplications+additions. Storage: n(n+1)/2 (lower triangle). For large sparse SPD systems (FEM stiffness matrices): sparse Cholesky with fill-reducing reordering (AMD, nested dissection) is standard. Incomplete Cholesky: for preconditioned conjugate gradient.
கோலஸ்கி: A என்பது SPD என்றால் உள்ளது. L_{kk}= sqrt(A_{kk} - sum_{j<k} L_{kj}^2) . பிவோட்டிங் இல்லாமல் எண்ணியல் ரீதியாக நிலையானது (மூலைவிட்ட உள்ளீடுகள் நேர்மறையாக இருக்கும்). விலை: n^3 /6 பெருக்கல்கள்+சேர்க்கைகள். சேமிப்பு: n(n+1)/2 (கீழ் முக்கோணம்). பெரிய ஸ்பேர்ஸ் SPD அமைப்புகளுக்கு (FEM விறைப்பு மெட்ரிக்குகள்): நிரப்பு-குறைக்கும் மறுவரிசைப்படுத்தலுடன் கூடிய ஸ்பேர்ஸ் கோலஸ்கி (AMD, உள்ளமை துண்டித்தல்) நிலையானது. முழுமையடையாத கோலஸ்கி: முன்நிபந்தனை செய்யப்பட்ட இணைச் சாய்வு.
Q4Easy
QR decomposition: A = QR where Q is orthogonal (Q^T*Q=I) and R is upper triangular. Applications include:
QR சிதைவு: A = QR இதில் Q ஆர்த்தோகனல் (Q^T *Q=I) மற்றும் R மேல் முக்கோணமாகும். பயன்பாடுகள் அடங்கும்:
- aOnly symmetric matrices — சமச்சீர் மெட்ரிக்குகள் மட்டுமே
- bLeast squares (solve min||Ax-b||^2: R*x=Q^T*b), eigenvalue computation (QR algorithm), and solving Ax=b more stably than LU for ill-conditioned A — குறைந்த சதுரங்கள் (நிமிடத்தை தீர்க்கவும்||Ax-b||^2: R*x= Q^T *b), eigenvalue computation (QR algorithm), மற்றும் Ax=b ஐ விட நிலையாக LU ஐ விட நிலையான Aக்கு தீர்வு✓ Correct
- cOnly square matrices — சதுர மெட்ரிக்குகள் மட்டுமே
- dOnly solving linear systems — நேரியல் அமைப்புகளை மட்டுமே தீர்க்கிறது
Explanation
QR decomposition: Householder reflections (O(2mn^2-2n^3/3) for m x n, m>=n, numerically stable). Gram-Schmidt (modified): O(2mn^2) flops, less stable. Applications: (1) Least squares: A^T*A*x=A^T*b is numerically worse; QR gives Rx=Q1^T*b directly. (2) QR algorithm for eigenvalues. (3) Rank-revealing QR (RRQR) for rank determination. The QR decomposition is the most important decomposition for overdetermined systems.
QR சிதைவு: வீட்டுப் பிரதிபலிப்புகள் (m x n, m>=n க்கு O(2mn^2-2n^3/3), எண்ணிக்கையில் நிலையானது). கிராம்-ஷ்மிட் (மாற்றியமைக்கப்பட்டது): O(2mn^2) தோல்விகள், குறைந்த நிலைத்தன்மை. பயன்பாடுகள்: (1) குறைந்த சதுரங்கள்: A^T *A*x= A^T *b என்பது எண்ணிக்கையில் மோசமானது; QR நேரடியாக Rx= Q1^T *b ஐ வழங்குகிறது. (2) eigenvalues க்கான QR அல்காரிதம். (3) ரேங்க்-ரீவீலிங் QR (RRQR) தர நிர்ணயம். QR சிதைவு என்பது மிகைப்படுத்தப்பட்ட அமைப்புகளுக்கு மிக முக்கியமான சிதைவு ஆகும்.
Q5Easy
The Conjugate Gradient (CG) method for solving Ax=b (A SPD): generates a sequence x_k minimizing the energy norm ||x-x_k||_A = sqrt((x-x_k)^T*A*(x-x_k)) over the Krylov space K_k(A,r_0) = span{r_0, Ar_0,...,A^{k-1}r_0}. The method converges in at most n iterations (exact arithmetic). In floating point:
Ax=b (A SPD) ஐத் தீர்ப்பதற்கான கான்ஜுகேட் கிரேடியன்ட் (CG) முறை: க்ரைலோவ் ஸ்பேஸ் K_k(A,r_0) = span{r_0, 2 span{r_0, 2 span {r_0, 2 span{r_0, 2 span இந்த முறை அதிகபட்சம் n மறு செய்கைகளில் (சரியான எண்கணிதம்) ஒன்றிணைகிறது. மிதக்கும் புள்ளியில்:
- aCG requires computing A^{-1} — CGக்கு A^{-1}ஐக் கணக்கிட வேண்டும்
- bCG always converges in exactly n/2 steps — CG எப்போதும் சரியாக n/2 படிகளில் ஒன்றிணைகிறது
- cCG diverges for ill-conditioned A — சீ.ஜி
- dCG is used as an iterative method (stopping early at convergence); convergence rate is governed by sqrt(kappa(A)) where kappa is the condition number: faster for well-conditioned A — CG ஒரு மறுசெயல் முறையாகப் பயன்படுத்தப்படுகிறது (ஒருங்கிணைந்த நிலையில் ஆரம்பத்தில் நிறுத்தப்படுகிறது); ஒருங்கிணைப்பு விகிதம் sqrt(kappa(A) ஆல் நிர்வகிக்கப்படுகிறது) இதில் கப்பா என்பது நிபந்தனை எண்: நன்கு சீரமைக்கப்பட்ட Aக்கு வேகமானது✓ Correct
Explanation
CG convergence: ||x-x_k||_A / ||x-x_0||_A <= 2*((sqrt(kappa)-1)/(sqrt(kappa)+1))^k. For kappa=100: rate=(9/11)^k -- about 35 iterations to reduce error by 10^6. For kappa=10^6: rate=(999/1001)^k -- about 7*10^6 iterations (very slow). Preconditioning: preconditioned CG (PCG) solves M^{-1}Ax=M^{-1}b where M is a good preconditioner (M~A but easily invertible). PCG convergence depends on kappa(M^{-1}A).
CG ஒருங்கிணைப்பு: ||x-x_k||_A / ||x-x_0||_A <= 2*(( sqrt(kappa) -1)/( sqrt(kappa) +1))^k. கப்பா=100க்கு: விகிதம்=( 9/11 )^k -- பிழையை 10^6 ஆல் குறைக்க சுமார் 35 மறு செய்கைகள். கப்பா=10^6: விகிதம்=( 999/1001 )^k -- சுமார் 7*10^6 மறு செய்கைகள் (மிக மெதுவாக). முன்நிபந்தனை: முன்நிபந்தனை செய்யப்பட்ட CG (PCG) M^{-1}Ax = K_k(A,r_0)0 ஐ தீர்க்கிறது, இதில் M ஒரு நல்ல முன்நிபந்தனையாகும் (M~A ஆனால் எளிதில் தலைகீழானது). PCG ஒருங்கிணைப்பு K_k(A,r_0)1 ஐச் சார்ந்தது.
20 more questions on Numerical Linear Algebra
Track your mastery, build a daily streak, and compete on the leaderboard across all 1 PG TRB subjects.