रैखिक समीकरण हल करना में

रैखिक समीकरण हल करना के बारे में

याद है, जब आपने हाई स्कूल में पहली बार बीजगणित सीखा था?

आम तौर पर हमें समीकरणों का एक समूह दिया जाता था और x तथा y का हल निकालने के लिए कहा जाता था।

4x - 3y = -2
2x + 7y = 16

दो समीकरण, दो अज्ञात राशियाँ: ज़रा-सा प्रतिस्थापन कीजिए, और आप जल्द ही देख लेंगे कि x = 1, y = 2।

अब पिछले उदाहरण के बाईं ओर फिर से ध्यान दीजिए। यह ऐसा दिखता है मानो मैट्रिक्स [4 -3; 2 7] किसी अज्ञात वेक्टर [x, y] को गुणा करके वेक्टर [-2, 16] दे रहा हो।

रैखिक बीजगणित के संकेतन में: A x = b, जहाँ मैट्रिक्स के लिए बड़े अक्षर और वेक्टर के लिए छोटे अक्षर लिखने की सामान्य परिपाटी अपनाई जाती है।

A x = 0 और नलस्पेस

एक महत्वपूर्ण विशेष स्थिति तब होती है जब हमारे सभी समीकरणों के दाईं ओर शून्य हो।

4x - 3y = 0
2x + 7y = 0

ऊपर के उदाहरण में एकमात्र हल x = y = 0 ही है, जो आम तौर पर दिलचस्प नहीं होता।

A x = 0 के गैर-तुच्छ हल तभी मौजूद होते हैं जब A का डिटरमिनेंट शून्य हो।

julia> using LinearAlgebra

julia> A = [4 -3; 2 7]
2×2 Matrix{Int64}:
 4  -3
 2   7

julia> det(A)  # not zero!
34.0

इसके बजाय इन समीकरणों को देखिए:

4x - 3y = 0
8x + 6y = 0

दूसरा समीकरण पहले समीकरण का ही दुगना है और कोई नई जानकारी नहीं देता। जिन भी मानों के लिए x = 0.75y हो, वे सभी हल होंगे।

ये (x, y) मान दो आयामों वाले स्पेस में एक रेखा पर पड़ते हैं। इसके अनंत हल होते हैं, और ये सभी मैट्रिक्स का नलस्पेस बनाते हैं।

इस स्थिति में मैट्रिक्स की पंक्तियाँ रैखिक रूप से स्वतंत्र नहीं होतीं, और मैट्रिक्स की रैंक पंक्तियों या स्तंभों की संख्या से कम होती है।

julia> A = [4 -3; 8 -6]
2×2 Matrix{Int64}:
 4  -3
 8  -6

julia> det(A)
0.0

julia> size(A)  # total number of rows and columns
(2, 2)

julia> rank(A)  # number of linearly-independent rows (or columns)
1

julia> nullspace(A)
2×1 Matrix{Float64}:
 -0.6
 -0.8

julia> nullspace(A) |> norm  # Julia returns unit vectors when possible
1.0

nullspace() फंक्शन एक ही बिंदु लौटाता है, जिसे इकाई वेक्टर तक सामान्यीकृत किया जाता है, लेकिन इस वेक्टर का कोई भी अदिश गुणज भी नलस्पेस में होता है।

A x = b को हल करना

अब मान लीजिए आपके पास 1000 अज्ञात राशियों वाले 1000 समीकरण हैं, तब क्या होगा? अगर यह बेतुका लगे, तो याद रखिए कि आज वायरलेस डिजिटल ट्रांसड्यूसर सस्ते और बहुमुखी हो गए हैं (विकृति, हवा की गति, तीन अक्षों वाला त्वरण, या जो कुछ भी हो, माप सकते हैं)। झूला पुल जैसी आधुनिक संरचना पर नज़र रखने के लिए उनमें से 1000 लगाना बिल्कुल उचित है। वहाँ एक ऐसा कंट्रोल सिस्टम होना चाहिए जो डेटा स्ट्रीम को पढ़े और हालात खतरनाक होने पर अलर्ट देने के लिए तैयार रहे।

फिर वही बात, A x = b, जहाँ हमारे पास A (इंजीनियरिंग डिज़ाइन से) और b (ट्रांसड्यूसर से मापे गए मान) हैं, पर हमें x निकालना है।

जो इससे परिचित नहीं है, उसका पहला ख्याल यही होता है कि किसी तरह A से "भाग देकर" उसे दाएँ पक्ष पर ले जाया जाए।

वास्तव में, A का व्युत्क्रम होता है (सभी वर्ग मैट्रिक्स का नहीं, पर लगभग सभी का: डिटरमिनेंट शून्य नहीं होना चाहिए), और यह गणना काम करती है (पर धीरे!)

julia> A = [4 -3; 2 7]
2×2 Matrix{Int64}:
 4  -3
 2   7

julia> b = [-2, 16]
2-element Vector{Int64}:
 -2
 16

# the inverse matrix
julia> inv(A)
2×2 Matrix{Float64}:
  0.205882   0.0882353
 -0.0588235  0.117647

julia> inv(A) * b
2-element Vector{Float64}:
 0.9999999999999999
 2.0

दुर्भाग्य से, व्युत्क्रम निकालना छोटे मैट्रिक्स के लिए धीमा है और बड़े मैट्रिक्स के लिए तो बेहद सुस्त। अगर गणना के दौरान ही आपका पुल गिर जाए, तो यह आदर्श नहीं है!

अच्छी बात यह है कि दूसरे एल्गोरिदम बहुत तेज़ हैं (इस मामले में गाउसीय विलोपन)।

Julia (Matlab की नकल करते हुए) सॉल्वर के लिए बस बैकस्लैश का उपयोग करता है (तकनीकी रूप से यह "बायाँ विभाजन" है)।

julia> x = A \ b
2-element Vector{Float64}:
 1.0
 2.0

यह एक साधारण उदाहरण है, पर कुछ बातों का ध्यान रखना ज़रूरी है।

• गुणांकों को स्तंभों में ठीक-ठीक जमना होता है, इसलिए जो पद छूट रहे हों उनके लिए ज़रूरत के अनुसार शून्य डाल दीजिए।
• समीकरणों (और इसलिए मैट्रिक्स की पंक्तियों) का रैखिक रूप से स्वतंत्र होना ज़रूरी है। अगर पंक्ति 3 केवल पंक्ति 1 और 2 का जोड़ है, तो वह कोई नई जानकारी नहीं देती और समस्या अल्प-निर्धारित हो जाती है।

rank() कमांड रैखिक रूप से स्वतंत्र पंक्तियों/स्तंभों की संख्या बताता है, इसलिए कोशिश कीजिए कि यह अज्ञात वेरिएबलो की संख्या के बराबर हो।

julia> rank(A)
2

आयताकार मैट्रिक्स

बचपन में, किशोरावस्था से पहले, आपको शायद यह पढ़ाया गया होगा कि N अज्ञात राशियाँ निकालने के लिए N समीकरणों का एक समूह चाहिए।

गणित की ज़्यादातर बातों की तरह, वास्तविकता थोड़ी और बारीक होती है (सिर्फ रैखिक स्वतंत्रता की वह बात नहीं, जो पिछले भाग में बताई गई थी)।

"बहुत कम" पंक्तियाँ

N-1 समीकरणों (यानी मैट्रिक्स A की पंक्तियों) के साथ समस्या अल्प-निर्धारित हो जाती है। तो क्या हम निराश होकर हार मान लें?

यह इस पर निर्भर करता है!

N-1 समीकरणों में अब भी बहुत जानकारी होती है। ज्यामितीय भाषा में कहें तो, हल को N-आयामी स्पेस में एक बिंदु के रूप में तय करने के लिए हमें N चाहिए, पर N-1 हमें बताएँगे कि हल कहीं एक रेखा पर ही होगा।

इससे हमारे पास अनंत हल तो रह जाते हैं, पर साथ ही पैरामीटर स्पेस का अनंत हिस्सा ऐसा भी होता है जहाँ कोई हल नहीं होता।

क्या आपके हलों की रेखा पैरामीटर स्पेस के किसी ऐसे हिस्से से गुज़रती है जिसकी चिंता किसी भी अच्छे इंजीनियर को होनी चाहिए? या जो इस बात को जायज़ ठहरा सके कि संरचना को आम लोगों के लिए बंद कर दिया जाए (तेज़ आड़ी हवाओं में झूला पुल काफी हिलने-डुलने लगते हैं)? शायद इसका पता लगाने के लिए कुछ और गणनाएँ करना फायदेमंद रहेगा!

julia> A3 = [4 -3 1; 2 2 2; 3 -4 -3]
3×3 Matrix{Int64}:
 4  -3   1
 2   2   2
 3  -4  -3

julia> b3 = [1, 12, -14]
3-element Vector{Int64}:
   1
  12
 -14

# fully-determined solution
julia> A3 \ b3
3-element Vector{Float64}:
 1.0
 2.0
 3.0

# remove row 3 from A3 and B3
julia> A2 = A3[1:2, :]
2×3 Matrix{Int64}:
 4  -3  1
 2   2  2

julia> b2 = b3[1:2]
2-element Vector{Int64}:
  1
 12

# an under-determined solution
julia> z1 = A2 \ b2
3-element Vector{Float64}:
 1.594594594594594
 2.445945945945947
 1.9594594594594592

बैकस्लैश सॉल्वर हमें एक हल दे देता है! अनौपचारिक रूप से, ऐसा लगता है कि यह सबसे छोटे नॉर्म वाला हल है (ज्यामितीय रूप से मूल बिंदु के सबसे नज़दीक)।

बाकी हल पाने के लिए हमें A2 का nullspace चाहिए।

मूल हल में नलस्पेस का कोई भी अदिश गुणज जोड़ने पर एक और मान्य हल मिल जाएगा।

# get the nummspace of A2
julia> N = nullspace(A2)
3×1 Matrix{Float64}:
 -0.46499055497527725
 -0.3487429162314578
  0.813733471206735

# add a random multiple of the nullspace to the earlier solution
julia> z = z1 + rand() * N
3×1 Matrix{Float64}:
 1.274331860650258
 2.205748895487695
 2.5199192438620472

# our random z is a valid solution, recovering b2 = [1, 12]
julia> A2 * z
2×1 Matrix{Float64}:
  0.9999999999999947
 12.0

इसी तरह, N-2 समीकरण (अनंत) हलों को एक समतल तक सीमित कर देंगे, और यही सिद्धांत लागू होते हैं।

"बहुत ज़्यादा" पंक्तियाँ

उलटी स्थिति तब आती है जब समीकरण अज्ञात राशियों से ज़्यादा हों, फिर भी वे रैखिक रूप से स्वतंत्र हों।

वास्तविक दुनिया की इंजीनियरिंग में यह बिल्कुल सामान्य है, और इसे अच्छी बात ही माना जाता है!

ट्रांसड्यूसर की परिशुद्धता सीमित होती है, b वेक्टर की परिशुद्धता सीमित होती है, और गणना में शोर भी होता है। अब हल शोर भरे डेटा पर न्यूनतम वर्ग फिट होता है।

सबसे आसान तरीका मैट्रिक्स के pseudoinverse का उपयोग करना है, जिसे Julia pinv() फंक्शन के रूप में लागू करता है।

इसका उपयोग किसी ऐसे वर्ग मैट्रिक्स के व्युत्क्रम की तरह किया जा सकता है जिसका व्युत्क्रम मौजूद हो, और यह सटीक हल के बजाय वेरिएबलो का न्यूनतम वर्ग अनुमान देता है।

# create 5-row A and b for 2 variables
julia> A5 = [4 -3; 2 7; -1 2; 1 -1; 3 1]
5×2 Matrix{Int64}:
  4  -3
  2   7
 -1   2
  1  -1
  3   1

julia> rank(A5)
2

# add some random-normal noise to b5
julia> b5n = [-2, 16, 3, -1, 5] + randn(5) * 0.1
5-element Vector{Float64}:
 -1.9337349223581917
 16.024913008059457
  3.0087646177373992
 -0.8675748721176717
  4.914568047308805

# solve to get x ≈ 1, y ≈ 2, using the pseudoinverse
julia> pinv(A5) * b5n
2-element Vector{Float64}:
 1.006117942769543
 1.9962973764508272

आइगेनवैल्यू और आइगेनवेक्टर

पिछले भाग में A x = b के हल बताए गए थे, जो हमारे परिचित बीजगणित जैसा ही है।

इस भाग में A x = λ x के हलों की बात है, जहाँ λ एक अदिश है।

यह रैखिक बीजगणित की एक खास अवधारणा है, पर हम इसे ज्यामितीय रूप से समझ सकते हैं:

x और λ के उपयुक्त मानों के लिए, वर्ग मैट्रिक्स A अशून्य वेक्टर x की लंबाई को λ के गुणक से बढ़ा-घटा देता है, पर उसकी दिशा नहीं बदलता (ऋणात्मक λ हो तो दिशा उलट जाती है)।

यह सुनने में भले ही सीमित काम की लगे, पर सचमुच यह बेतहाशा उपयोगी निकलती है!

शब्दावली: λ के मान्य मान A के आइगेनवैल्यू हैं, और x के संगत मान A के आइगेनवेक्टर हैं। दुर्भाग्य से, ऐसे शब्दों के साथ जीना ही पड़ता है जो बीच में ही भाषा बदल देते हैं।

विद्यार्थियों को आम तौर पर 2×2 मैट्रिक्स के आइगेनवैल्यू/आइगेनवेक्टर हाथ से निकालना सिखाया जाता है, पर कंप्यूटर से यह बहुत आसान है (हालाँकि यह फिर भी काफी धीमा है, और सामान्य स्थिति में n×n मैट्रिक्स के लिए O(n^3) के क्रम में बढ़ता है)।

julia> A = rand(-9:9, 2, 2)
2×2 Matrix{Int64}:
 9  5
 3  2

julia> F = eigen(A)
Eigen{Float64, Float64, Matrix{Float64}, Vector{Float64}}
values:
2-element Vector{Float64}:
  0.27984674554472466
 10.720153254455274
vectors:
2×2 Matrix{Float64}:
 -0.497417  0.945605
  0.867511  0.325317

# eigenvalues
julia> F.values
2-element Vector{Float64}:
  0.27984674554472466
 10.720153254455274

# each column is an eigenvector, normalized to a unit vector
julia> F.vectors
2×2 Matrix{Float64}:
 -0.497417  0.945605
  0.867511  0.325317

आम तौर पर, एक n×n मैट्रिक्स के n आइगेनवैल्यू होते हैं, हालाँकि उनके मान हमेशा अलग-अलग नहीं होते। इन्हें n घात वाले बहुपद (जिसे अभिलाक्षणिक बहुपद कहते हैं) के मूल समझिए; ये दोहराए जा सकते हैं और वास्तविक मानों वाले मैट्रिक्स के लिए भी अक्सर सम्मिश्र होते हैं।

हर आइगेनवेक्टर एक दिशा दर्शाता है, और उसका कोई भी अदिश गुणज भी एक मान्य आइगेनवेक्टर होता है। आगे की गणनाओं की सुविधा के लिए Julia ऐसे इकाई वेक्टर लौटाता है जिनका नॉर्म 1 होता है।

अनुप्रयोग

आइगेनवेक्टर क्यों ज़रूरी हैं, यह समझाना आदर्श रूप से कुछ छोटे अनुच्छेदों के बजाय 500 पन्नों की किसी पाठ्यपुस्तक का काम है। यह विषय आधुनिक अनुप्रयुक्त गणित के बहुत बड़े हिस्से में फैला हुआ है।

मोटे तौर पर कहें तो, आइगेनवेक्टर किसी डेटासेट के "सबसे ज़रूरी" अक्षों (दिशाओं) को दर्शाते हैं। आइगेनवैल्यू हर अक्ष का "सापेक्ष महत्व" बताते हैं (बशर्ते इनपुट के सामान्यीकरण से जुड़ी कुछ मान्यताएँ मान ली जाएँ)।

यह वास्तव में क्या मतलब रखता है, यह उपयोग पर निर्भर करता है।

प्रमुख घटक विश्लेषण

डेटा साइंस की किसी आम समस्या में हमारे पास 100 या उससे ज़्यादा "फीचर" हो सकते हैं, जो डेटा के स्तंभों के रूप में रखे जाते हैं। लगभग हमेशा ही उसमें शोर, दोहराव और अनचाहे सहसंबंध मौजूद होते हैं।

हमें आयाम कम करने की ज़रूरत होती है, और इस अव्यवस्था में क्रम लाने का एक तरीका PCA है:

• डेटा का कोवेरिएंस मैट्रिक्स निकालिए।
• अब हमारे पास एक वर्ग मैट्रिक्स है, तो इसके बाद आइगेनवैल्यू और आइगेनवेक्टर निकालिए।
• आइगेनवेक्टरों को उनके आइगेनवैल्यू के घटते क्रम में लगाइए (अधिक सटीक रूप से, |λ| के मान के अनुसार)।
• अब सबसे ऊपर के k आइगेनवेक्टर ही आपके principal components हैं, जहाँ k फीचरों की मूल संख्या से काफी छोटा होता है।
• पूरे डेटासेट को इन k अक्षों पर प्रक्षेपित कीजिए, और दिलचस्प पैटर्न ढूँढना शुरू कीजिए।

इस रूप में PCA का उपयोग ऐसे अलग-अलग समूहों ने किया है: चिकित्सा वैज्ञानिक, जो दवा डिज़ाइन में अणुओं के गुण बेहतर बनाने पर काम करते हैं, और राजनीतिक प्रचारक, जो सर्वेक्षण के डेटा से मतदाताओं की पसंद समझने की कोशिश करते हैं। शायद मार्केटिंग करने वाले समूह भी, जो आपको कुछ बेचना चाहते हैं, पर हर तकनीक का इस्तेमाल अच्छे या बुरे, किसी भी काम के लिए किया जा सकता है।

PCA, Julia की न्यूनतम इंस्टॉलेशन का हिस्सा नहीं है, पर (Exercism के बाहर) MultivariateStats पैकेज में वह सब मिल जाता है जिसकी आपको ज़रूरत है।

इमेज प्रोसेसिंग

PCA के विचार को एक कदम आगे बढ़ाएँ तो, डिजिटल इमेज दरअसल पिक्सल मानों के मैट्रिक्स ही होती हैं, और हम उनके लिए प्रमुख घटक निकाल सकते हैं।

दशकों से इसका उपयोग इमेज कंप्रेशन में होता आया है, जहाँ फाइल का आकार घटाते समय क्या बनाए रखना सबसे ज़रूरी है, इसमें PCA मार्गदर्शन करता है।

आजकल PCA, चेहरा पहचानने जैसे इमेज क्लासिफायरों का एक अहम हिस्सा बनता जा रहा है। अगली बार जब आप किसी हवाई अड्डे से गुज़रें, तो बिग ब्रदर सिर्फ देख ही नहीं रहा होता, वह जो देखता है उसे समझने के लिए रैखिक बीजगणित का भी उपयोग करता है!

मैकेनिकल इंजीनियरिंग

कम विवादास्पद बात यह है कि किसी यांत्रिक कंपोनेंट के प्रमुख अक्ष उसके जड़त्व आघूर्ण टेंसर I के आइगेनवेक्टर होते हैं (यह एक मैट्रिक्स ही है, बस नाम थोड़ा अलग है)।

आपकी कार के हर पहिए पर शायद एक या अधिक बैलेंस वज़न लगे होते हैं, जिन्हें इस टेंसर I के विकर्णेतर एलिमेंटों को शून्य करने के लिए ठीक किया जाता है। गैराज का मैकेनिक निश्चित रूप से यह गणित करने से बचता है (हवाई जहाज़ के डिज़ाइनरों और रॉकेट इंजीनियरों के उलट), पर "डगमगाना" बस एक आम शब्द है जो टेंसर के इन क्रॉस-टर्मों को बताता है; ये टर्म इस स्थिति में आपकी यात्रा कम आरामदेह बना देते हैं और बेयरिंगों पर यांत्रिक घिसाव बढ़ा देते हैं।