Doğal kübik spline. Kübik eğriler

Gemi yapımı, otomobil imalatı ve uçak yapımı gibi endüstriyel imalatta, nihai şekil, nihai şekil veya buna yakın ölçekte, bitirme işlemi yoluyla belirlenir.

Temsil edilen bu sürecin otomasyonu önemli ilgi bilgisayar grafikleri için. Matematiksel spline'ın şekli, fiziksel spline'ın konturunu takip eder (Şekil 5-4), yani. belirli noktalardan geçen esnek ahşap veya plastik cetvel. Spline'ın şeklini değiştirmek için kurşun ağırlıklar kullanılır. Sayılarını ve konumlarını değiştirerek ortaya çıkan eğriyi daha düzgün, daha güzel ve "göze hoş" hale getirmeye çalışırlar.

Fiziksel bir spline'ı ince, esnek bir şerit olarak düşünürsek, şekli (sapması), şerit boyunca bükülme momenti için Euler denklemi (5-2) ile belirlenir:

burada raf malzemesinin özelliklerine bağlı olan Young modülü, eğrinin şekliyle belirlenen atalet momentidir ve eğrilik yarıçapıdır.

Küçük sapmalar için yarıçap yaklaşık olarak eşittir

,

burada asal, direk boyunca mesafeye göre türevi belirtir ve asalın sapmasıdır. Euler denklemi şu şekli alır

Ağırlıkların basit destek görevi görmesine izin verin, ardından aralarındaki bükülme momenti doğrusal olarak değişir. Değiştirme Euler denkleminde şunu elde ederiz:

ve çift entegrasyondan sonra

Böylece spline'ın şekli kübik bir polinom tarafından verilir.

İÇİNDE Genel dava Matematiksel bir spline, bölümlerin bağlantı noktalarında derecenin sürekli türevine sahip parçalı bir derece polinomudur. Örneğin kübik bir spline, bağlantı noktalarında ikinci dereceden sürekliliğe sahiptir. Düşük dereceli polinomlardan parçalı eğriler, büyük hesaplama maliyetleri gerektirmedikleri ve polinomların karakteristik sayısal sapmalarına neden olmadıkları için eğrilerin enterpolasyonu için çok uygundur. yüksek sipariş. Fiziksel spline'lara benzer şekilde, her bir parçanın iki noktadan geçtiği bir dizi kübik parça tipik olarak kullanılır. Kübik bir spline da uygundur çünkü en küçük dereceden bir eğridir, bükülme noktalarına ve uzayda bükülmeye izin verir.

Bir parametrik spline segmentinin denklemi şöyledir:

, , (5-1)

segmentin başında ve sonundaki parametre değerleri nerede ve nerededir. - segmentin herhangi bir noktasına vektör. üç bileşenin olduğu vektör değerli bir fonksiyondur Kartezyen koordinatları vektör.

Pirinç. 5-5 Kübik bir spline'ın bir segmenti.

Her bileşenin benzer bir formu vardır;

, ,

, ,

, .

Sabit katsayılar, spline segmenti için dört sınır koşuluna göre hesaplanır. Denklemi (5-1) forma yazalım.

ve, parçanın uçlarının vektörleri olsun (bkz. Şekil 5-5). Ayrıca ve 'ye göre türevler doğru parçasının uçlarında teğet vektörler olsun. Diferansiyel denklem (5-1), şunu elde ederiz:

, . (5-3)

Sonucu yazalım

, . (5-4)

Genelliği kaybetmeden şunu varsayalım ve sınır koşullarını uygulayalım.

Bilinmeyenler için dört denklem elde ederiz:

, (5-6b)

, (5-6c)

. (5-6g)

Çözümler ve forma sahip:

(5-7a)

. (5-7b)

, , ve miktarları kübik spline'ın segmentini belirtir. Açıkçası, bir parçanın şekli parçanın uçlarındaki konuma ve teğet vektörlere bağlıdır. Daha sonra, sonuçların segmentin sonunda parametre değerini içerdiğini unutmayın. Her uç nokta ve teğet vektörün üç bileşeni olduğundan, kübik uzay eğrisinin parametrik denklemi on iki vektör bileşenine ve parçanın sonundaki parametrenin değerine bağlıdır.

Denklemleri (5-6) ve (5-7) (5-1)'de değiştirerek, kübik bir spline'ın bir parçası için denklemi elde ederiz:

. (5-8)

Bu bir segment için bir denklemdir. Eğrinin tamamını elde etmek için birçok segmenti bağlamanız gerekir. İncirde. Şekil 5-6 iki bitişik parçayı göstermektedir. Vektörler, , , teğet vektörler ve parametrelerin değerleri biliniyorsa, her bir parçanın şekli denklem (5-8) ile belirlenir. Ancak bağlantı noktasındaki teğet vektörün bilinmesi pek mümkün değildir. Neyse ki süreklilik koşulundan türetilebilir.

Parçalı dereceli bir spline'ın birleşme noktalarında derece sürekliliğine sahip olduğunu hatırlayın; kübik bir spline'ın sürekliliği ikidir. Bunu yapmak için çizginin ikinci türevi veya eğriliği sürekli olmalıdır. Denklemin (5-1) iki kere diferansiyelini alırsak, şunu elde ederiz:

, . (5-9)

Pirinç. 5-6 İki parçalı kübik spline segmenti.

Spline'ın ilk parçası için parametre . Denklemde (5-9) yerine koyalım:

.

Spline'ın ikinci bölümü için parametre aralıkta değişir. İkinci bölümün başındaki değeri denklem (5-9)'a koyalım

Elde edilen sonuçları eşitleyip (5-6a,b) ve (5-7a) denklemlerini kullanarak şunu elde ederiz:

.

Bu denklemin sol tarafı birinci parçanın sonundaki eğriliği, sağ tarafı ise ikinci parçanın başındaki eğriliği temsil eder. Terimleri çarpın ve gruplandırın:

Bu, bağlantı noktasındaki bilinmeyen teğet vektörü belirler. Son denklemin yine segmentlerin uçlarında parametre değerleri içerdiğini unutmayın.

Ortaya çıkan formül noktalar için genelleştirilebilir ve kübik bir spline'ın bölümleri için bağlantı noktalarında ikinci dereceden süreklilik elde edilebilir.

Pirinç. 5-7 Parçalı kübik spline segmentleri seti için gösterimler.

Herhangi iki bitişik spline segmenti için genelleştirilmiş denklem ve Şekil 2'deki gösterimde. 5-7 şuna benzer:

(5-11)

ilk bölüm için ve

(5-12)

ikincisi için, her bölüm için parametre birinci ve ikinci için sıfırdan değişmeye başladığından - .

Herhangi bir bitişik parçanın birleşme noktalarında ikinci türevleri eşitlemek, , verir genel sonuç, denkleme eşdeğer (5-10),

buradan herhangi iki parçanın bağlantı noktalarında teğet vektör belirlenir ve .

Spline'ın tüm bölümleri için denklemin (5-13) yinelemeli kullanımı, teğet vektör denklemleri üretir. İÇİNDE matris formu:

(5-14)

Matris kare değildir, çünkü yalnızca vektörler için denklemler vardır ve bir çözüm elde etmek için ters çevrilemez. Eğrinin uçlarındaki teğet vektörlerin bilindiğini varsayarsak sorun çözülür. Şimdi matris şuna benziyor

(5-15)

matrisin kare ve tersinir olduğu yer. Ayrıca bunun ters çevrilmesinin hesaplama maliyetlerini azaltan üç köşegen olduğuna da dikkat edin. Ayrıca matris çapraz olarak baskındır. Bundan şu sonuç çıkıyor: tek karar:

. (5-16)

Eğer bilirsek, her bir spline segmenti için katsayıları belirlemek kolaydır. (5-6)-(5-11) denklemlerini genelleştirerek şunu elde ederiz:

,

.

O zamandan beri ve Vektör nicelikleri, o zaman onlar da vektördür; eğer bileşenleri varsa, o zaman bu bileşenlere de sahiptirler.

Matris formunda herhangi bir spline parçasının denklemi şöyledir:

. (5-17)

Uçlarında teğet vektörler bulunan ve noktalardan geçen kübik bir eğrinin belirtilmesi gereksin. Denklem (5-16)'dan iç teğet vektörleri , buluruz. Daha sonra denklem (5-17)'den her parçanın uçlarının bilinen koordinatları ve her parça için teğet vektörleri belirlenir. Denklemin son genellemesi (5-1)

, , , (5-18)

Spline segmentini hesaplamak için kullanılır.

Matris formunda denklem (5-18) şuna benzer:

, . (5-19)

Denklemi (5-17) değiştirerek ve terimleri yeniden düzenleyerek şunu elde ederiz:

, , , (5-20)

, (5-21a)

, (5-21b)

, (5-21s)

, (5-21g)

ağırlık fonksiyonları denir.

Pirinç. 5-8 Kübik spline ağırlıklandırma fonksiyonları

Bu tanımları kullanarak denklem (5-20)'yi matris formunda yazıyoruz.

ağırlık fonksiyonunun matrisi nerede

geometrik bilgiler içerir. Aşağıda görüldüğü gibi (5-22) gibi denklemler, yani. genellikle eğrileri ve yüzeyleri tanımlamak için kullanılan, geometrik koşullar matrisiyle çarpılan bir ağırlıklandırma fonksiyonu matrisidir.

Denklem (5-21)'den her ağırlık fonksiyonunun üçüncü dereceden olduğu açıktır. Kübik bir spline parçası üzerindeki herhangi bir nokta, uç noktaların ve teğet vektörlerin ağırlıklı toplamıdır. Katsayılar ağırlıklandırma fonksiyonları olarak işlev görür. İncirde. 5-8 için gösterilmektedir. Şekilden açıkça görülmektedir ki ve , yani. eğri nokta vektöründen geçer. Benzer şekilde ve yani. eğri aynı zamanda nokta vektöründen de geçer. Daha sonra ve ve ve simetrisine dikkat edelim. Aslında . Son olarak , , ve 'nin göreceli sırasına dikkat edelim. Büyüklükteki önemli fark, genel olarak uç noktaların konumunun teğet vektörlerden daha büyük bir etkiye sahip olduğunu göstermektedir.

Parçalı kübik bir spline'ın noktalarla, teğet vektörlerle ve parametre değerleriyle, yani tüm bölümlerin uçlarında tanımlandığını hatırlayın. Seçim eğrinin düzgünlüğünü etkiler.

İkinci türevin iç bağlantı noktalarındaki sürekliliği, kendi başına, eğri boyunca minimum eğrilik anlamında eğrinin düzgünlüğünü garanti etmez. Uygun değerleri seçerek, her bölüm için katsayıları en aza indirmek ve eğrinin daha düzgün olmasını sağlamak mümkündür. Tipik olarak bu ek hesaplamalara gerek yoktur. Pratik amaçlar için, birden fazla basit yöntemler, burada tartışılanlar gibi.

Hesaplama yöntemlerinden biri parametre değerlerini ayarlamaktır eşit uzunluklar Bitişik noktalar arasındaki akorlar. Aynı zamanda eğrinin kalitesi çoğu kullanıcının gereksinimlerini karşılar uygulamalı problemler. Diğer bir yöntem ise varyasyonu normalleştirmektir. bire eşit her spline segmenti için. Bu seçim hesaplamaları basitleştirir (bkz. Bölüm 5-4). Yukarıdaki denklemlerden de görülebileceği gibi, herhangi bir seçim farklı katsayılara ve dolayısıyla farklı eğrilerin geçmesine neden olur. verilen puanlar.

Bir örneğe bakalım.

Verilen sınır noktaları boyunca düzgün eğriler çizme problemini veya enterpolasyon problemini ele alalım. İki noktadan herhangi bir sayıda düzgün eğri çizilebildiğinden, bu sorunu çözmek için istenen eğriyi belirleyecek fonksiyon sınıfını sınırlamak gerekir. Matematiksel eğriler eğrilere yaklaşmak için kullanılan işlevlerdir. Önemli özellikleri hesaplama kolaylığıdır. Pratikte üçüncü derece polinom tipindeki splinelar sıklıkla kullanılır. Onların yardımıyla, insanın öznel pürüzsüzlük kavramına sezgisel olarak karşılık gelen eğriler çizmek oldukça uygundur. "Spline" terimi İngilizce spline kelimesinden gelir; bu, teknik ressamlar tarafından örneğin gemilerin veya uçakların dış hatlarını oluşturmak için yumuşak eğriler çizmek için kullanılan esnek bir çelik şerit anlamına gelir.

İlk önce tek değişkenli bir fonksiyonun grafiğini çizmek için bir spline fonksiyonu düşünelim. Düzlemde , , ve noktalarının bir dizisi verilsin. Gerekli fonksiyonu tanımlayalım ve iki koşulu ayarlayalım:

1) Fonksiyon verilen tüm noktalardan geçmelidir: , .

2) Fonksiyon iki kez sürekli türevlenebilir olmalı, yani tüm aralıkta sürekli bir ikinci türevi olmalıdır.

Segmentlerin her birinde fonksiyonumuzu üçüncü dereceden bir polinom biçiminde arayacağız:

.

Pirinç. 40. Spline işlevi.

Bir polinom oluşturma görevi katsayıları bulmaktan ibarettir. Segmentlerin her biri için 4 katsayı bulmak gerektiğinden, gerekli katsayıların toplam sayısı olacaktır. Tüm katsayıları bulmak için karşılık gelen denklem sayısını belirleriz. İlk denklemler, fonksiyon değerlerinin iç düğümlerdeki çakışma koşullarından elde edilir. Aşağıdaki denklemler birinci ve ikinci türevlerin değerlerinin iç düğümlerde çakışması koşullarından da benzer şekilde elde ederiz. İlk koşulla birlikte denklemleri elde ederiz. Eksik iki denklem, segmentin uç noktalarındaki birinci türevlerin değerleri belirtilerek elde edilebilir. Bu şekilde sınır koşulları belirlenebilir.

Daha fazlasına geçelim zor durum– eğrilerin ayarlanması üç boyutlu uzay. Bir eğrinin fonksiyonel spesifikasyonu durumunda, kendi kendine kesişme durumunda belirsizlik ve türevlerin değerleri eşit olduğunda rahatsızlık mümkündür. Bunu göz önünde bulundurarak, bir fonksiyon arayacağız. parametrik form. şeklinde bağımsız bir parametre olsun. Biz buna kübik parametrik spline diyoruz aşağıdaki sistem denklemler:

Eğri üzerindeki noktaların koordinatları vektör tarafından tanımlanır ve üç türev, noktadaki karşılık gelen teğet vektörün koordinatlarını belirtir. Örneğin koordinat için:

.

Parametrik bir kübik spline belirtmenin bir yolu, başlangıç ​​ve başlangıç ​​koordinatlarını belirtmektir. bitiş noktaları ve bunların içindeki teğet vektörler. Bu belirleme şekline Hermite formu denir. Uç noktalarını ve , ve bunlara teğet vektörleri ve ’yi gösterelim. Endeksler daha sonraki sunum dikkate alınarak bu şekilde seçilmiştir.

Geri kalan iki denklem için katsayılar benzer şekilde bulunduğundan dört katsayıyı bulma problemini çözeceğiz. Bir spline oluşturmanın koşulunu yazalım:

için ifadeyi yeniden yazalım. vektör formu:

.

Vektör dizisini gösterelim ve katsayıların bir vektör sütunu, o zaman .

(*)'dan şu sonuç çıkıyor: , . Teğetler için ,

Buradan vektör-matris denklemini elde ederiz:

.

Bu sistem bularak çözülebilir. ters matris boyut .

.

İşte bir Hermit matrisi, - geometrik vektör Ermita. Bulmak için ifadeyi değiştirelim: . Benzer şekilde diğer koordinatlar için: , .

Spline noktalarının koordinatlarını hesaplamak için açık formüller yazalım. O zamandan beri sağdan ile çarparak şunu elde ederiz:

.

Parantez içindeki dört fonksiyona eşlenik fonksiyonlar denir.

Hermite formunda verilen bir eğrinin şekli, teğet vektörün yönünün şu şekilde verildiğini dikkate alırsak kolaylıkla değiştirilebilir: başlangıç ​​yönü ve teğet vektörün modülü, Şekil 2'de gösterildiği gibi eğrinin bu vektör yönündeki uzama derecesini belirtir. 41.

Pirinç. 41. Hermite formundaki parametrik spline. Eğrinin sağa doğru uzaması şu şekilde sağlanmaktadır.

Sınır koşullarını belirleme açısından Hermite formundan farklı olan, yani vektörler yerine noktalar (ve karşılık gelen yarıçap vektörleri) kullanan ve Şekil 42'de gösterildiği gibi koşullar şöyle olacak şekilde tanıtılan Bezier formunu ele alalım. karşılanır: Ve .

Pirinç. 42. Bezier formunda parametrik spline.

Hermite formundan Bezier formuna geçiş şu dönüşümle gerçekleştirilir:

, (*)

geometrik Bezier vektörü nerede. Bunu ifadesinin yerine koyarsak, şunu elde ederiz:

Bezier eğrilerinin yararlı bir özelliği, eğrinin her zaman dörtgenin oluşturduğu dışbükey gövdenin içinde yer almasıdır. Bu özellik (*) ifadesinde katsayıların 0'dan 1'e kadar değerler alması ve toplamlarının bire eşit olması kullanılarak kanıtlanabilir.

Matrisin formda olduğuna dikkat edin

- Bezier matrisi denir.

Kaynakça

1. Newman, Sproull, İnteraktif Bilgisayar Grafiğinin Temelleri, M. Mir, 1976.

2. Melek Y. Pratik giriş bilgisayar grafikleri alanında, Radyo ve İletişim, 1984.

3. A. Van-Dam, J. Foley, İnteraktif Bilgisayar Grafiğinin Temelleri, cilt 1-2, M. Mir, 1985.

4.E.V. Zhikin, A.V.Boreskov, Bilgisayar grafikleri. Dinamikler, gerçekçi görüntüler, M., Dialog-MEPhI, 1995, 1997.

5. L. Ammeral, C dilinde bilgisayar grafikleri, 4 cilt halinde, Sol. Sistem, 1992.

6. Bilgisayar zeka kazanır. Başına. İngilizceden Ed. V.L.Stefanyuk, M.Mir, 1990.

7. Rogers, bilgisayar grafiğinin algoritmik temelleri. M. Mir, 1989.

8. Grice, Kişisel bilgisayarların grafik araçları, M., Mir, 1980.

9. Rogers, Adams, Matematiksel Temeller makine grafikleri, M. Makine mühendisliği, 1985.

10. Giloy, İnteraktif bilgisayar grafikleri, M., Mir, 1981.

11. F. Preparata, M. Sheimos, Hesaplamalı geometri: Giriş, M. Mir, 1989.

12. A. Fox, M. Pratt, Hesaplamalı Geometri, M., Mir, 1982.

13. A.B. Boreskov, E.V. Shikina, G.E. Shikina, Bilgisayar grafikleri: ilk tanışma, Ed. E.V. Shikina, M., Finans ve İstatistik, 1996.

14. A.V. Frolov, G.V. Frolov, MS WINDOWS'ta GDI grafik arayüzü, Moskova, Dialogue-MEPhI Yayınevi, 1994.

15. Michael Laszlo, Hesaplamalı Geometri ve bilgisayar grafikleri C++, Moskova, Binom, 1997.

16. Yu. Tikhomirov, Üç boyutlu grafiklerin programlanması, St. Petersburg: BHV-St. Petersburg, 1999.

17. A. Khonich, Kendi başınıza üç boyutlu bir oyun nasıl oluşturulur? M.: MİKROART, 1996.

18. M. Marov, 3D Studio MAX 2.5: referans kitabı - St. Petersburg: “Peter”, 1999. – 672 s.

19. A. La Mote, D. Ratcliffe ve diğerleri Oyun programlamanın sırları / İngilizceden çevrilmiştir. – St. Petersburg: Peter, 1995. – 720 s.

20. N. Thompson, Windows 95 için üç boyutlu grafik programlamanın sırları. İngilizce'den çeviri. – St. Petersburg: Peter, 1997. – 352 s.

* Bu tanımda, diyelim ki Oz ekseni Ox ekseni ile değiştirilirken, kalan eksenler döngüsel permütasyon kuralına göre değiştirilir, yani Oy, Oz ile, Ox ise Oy ile değiştirilir. Üç döngüsel permütasyon olabilir: (x,y,z)®(y,z,x)®(z,x,y).

* Daha katı tanım homojen koordinatlar bölümde verilmiştir lineer Cebir"Projektif uzaylar".

YÜZEYLERİN NOKTA NOKTA AÇIKLAMASI.

Yöntem, bir yüzeyin kendisine ait bir dizi noktayla belirlenmesinden oluşur. Sonuç olarak bu yöntemle görüntü kalitesi noktaların sayısına ve konumlarına bağlıdır.

Nokta nokta açıklama Yüzeyin çok karmaşık olduğu ve düzgünlüğün olmadığı durumlarda kullanılan ve ayrıntılı bir gösterim geometrik özellikler pratik için önemlidir.

Örnek: Diğer gezegenlerdeki toprak alanları, şekiller gök cisimleri Uydu görüntüleri sonucunda elde edilen bilgiler. Elektron mikroskobu kullanılarak alınan mikro nesneler.

Noktasal olarak tanımlanan nesnelere ilişkin ilk bilgiler bir matris biçiminde sunulur 3 boyutlu koordinatlar puan.

Spline'lar verilen fonksiyonları temsil etmek için kullanılabilen düzgün (birkaç sürekli türevi olan) parçalı polinom fonksiyonlardır büyük miktar değerler ve tek bir polinomla yaklaşımın uygulanamadığı değerler. Spline'lar düzgün, ekonomik ve kullanımı kolay olduğundan, aşağıdakiler için isteğe bağlı fonksiyonların oluşturulmasında kullanılırlar:

o eğri modelleme;

o eğrileri kullanarak veri yaklaşımı;

o fonksiyonel yaklaşımların gerçekleştirilmesi;

o Fonksiyonel denklemlerin çözülmesi.

Verilen sınır noktaları boyunca düzgün eğriler çizme problemini veya enterpolasyon problemini ele alalım. İki noktadan herhangi bir sayıda düzgün eğri çizilebildiğinden, bu sorunu çözmek için istenen eğriyi belirleyecek fonksiyon sınıfını sınırlamak gerekir. Matematiksel eğriler eğrilere yaklaşmak için kullanılan işlevlerdir. Önemli özellikleri hesaplama kolaylığıdır. Uygulamada, üçüncü dereceden polinomlar şeklindeki spline'lar sıklıkla kullanılır. Onların yardımıyla, insanın öznel pürüzsüzlük kavramına sezgisel olarak karşılık gelen eğriler çizmek oldukça uygundur. "Spline" terimi İngilizce spline kelimesinden gelir; bu, teknik ressamlar tarafından örneğin gemilerin veya uçakların dış hatlarını oluşturmak için yumuşak eğriler çizmek için kullanılan esnek bir çelik şerit anlamına gelir.

İlk önce tek değişkenli bir fonksiyonun grafiğini çizmek için bir spline fonksiyonu düşünelim. Düzlem üzerinde bir dizi nokta verilsin ve . Gerekli fonksiyonu tanımlayalım ve iki koşulu belirleyelim:

1) Fonksiyon tüm noktalardan geçmelidir: , ;

2) Fonksiyon iki kez sürekli türevlenebilir olmalı, yani tüm aralıkta sürekli bir ikinci türevi olmalıdır.

Segmentlerin her birinde üçüncü dereceden polinom biçiminde fonksiyonumuzu arayacağız:

.

Spline işlevi

Bir polinom oluşturma görevi katsayıları bulmaktan ibarettir. Segmentlerin her biri için 4 katsayı bulmak gerektiğinden, gerekli katsayıların toplam sayısı olacaktır. Tüm katsayıları bulmak için karşılık gelen denklem sayısını belirleriz. İlk denklemler, fonksiyon değerlerinin iç düğümlerdeki çakışma koşullarından elde edilir. Aşağıdaki denklemler, birinci ve ikinci türevlerin değerlerinin iç düğümlerdeki çakışma koşullarından benzer şekilde elde edilir. İlk koşulla birlikte denklemleri elde ederiz. Eksik iki denklem, segmentin uç noktalarındaki birinci türevlerin değerleri belirtilerek elde edilebilir. Bu şekilde sınır koşulları belirlenebilir.

Üç boyutlu uzayda eğrileri tanımlayan daha karmaşık bir duruma geçelim. Bir eğrinin fonksiyonel spesifikasyonu durumunda, kendi kendine kesişme durumunda belirsizlik ve türevlerin değerleri eşit olduğunda rahatsızlık mümkündür. Bunu göz önünde bulundurarak fonksiyonu parametrik formda arayacağız. şeklinde bağımsız bir parametre olsun. Aşağıdaki denklem sistemine kübik parametrik spline adını verelim:

Eğri üzerindeki noktaların koordinatları vektör tarafından tanımlanır ve üç türev, noktadaki karşılık gelen teğet vektörün koordinatlarını belirtir. Örneğin koordinat için:

Parametrik bir kübik spline belirtmenin bir yolu, başlangıç ​​ve bitiş noktalarının koordinatlarının yanı sıra bu noktalardaki teğet vektörleri belirtmektir. Bu belirleme şekline Hermite formu denir. Uç noktalarını ve , ve bunlara teğet vektörleri ve ’yi gösterelim. Endeksler daha sonraki sunum dikkate alınarak bu şekilde seçilmiştir.

Geri kalan iki denklem için katsayılar benzer şekilde bulunduğundan dört katsayıyı bulma problemini çözeceğiz. Bir spline oluşturmanın koşulunu yazalım:

İfadesini vektör biçiminde yeniden yazalım:

.

Katsayıların satır vektörünü ve sütun vektörünü gösterelim, o zaman .

(*)'dan şu anlaşılıyor; . Teğetler için ,

Buradan vektör-matris denklemini elde ederiz:

.

Bu sistem boyutun ters matrisi bulunarak çözülür.

.

İşte Hermit matrisi ve geometrik Hermit vektörü. Bulmak için ifadeyi değiştirelim: . Benzer şekilde diğer koordinatlar için: , .

Bulunan eğriler ve yüzeyler pratik problemler, çoğu zaman oldukça karmaşık şekil evrensel olmasına izin vermeyen analitik görev genel olarak yardımla temel işlevler. Bu nedenle, her biri bir veya iki değişkenin temel fonksiyonları kullanılarak oldukça tatmin edici bir şekilde tanımlanabilen nispeten basit düzgün parçalardan - bölümler (eğriler) veya kesikler (yüzeyler) birleştirilirler. Bu durumda kısmi eğriler veya yüzeyler oluşturmak için kullanılan düzgün fonksiyonların benzer nitelikte olmasını, örneğin polinom olmasını gerektirmesi oldukça doğaldır. aynı derecede. Ortaya çıkan eğrinin veya yüzeyin yeterince pürüzsüz olması için, karşılık gelen parçaların birleştiği yerde özellikle dikkatli olmanız gerekir. Polinomların derecesi basit geometrik hususlara göre seçilir ve kural olarak küçüktür. Bileşik eğrinin tamamı boyunca teğeti düzgün bir şekilde değiştirmek için, birleştirilmiş eğrileri üçüncü dereceden polinomlar kullanarak tanımlamak yeterlidir, kübik polinomlar. Bu tür polinomların katsayıları her zaman karşılık gelen bileşik eğrinin eğriliği sürekli olacak şekilde seçilebilir. Tek boyutlu problemleri çözerken ortaya çıkan kübik eğriler, kompozit yüzey parçalarının yapımına uyarlanabilir. Ve burada iki değişkenin her birinde üçüncü dereceden polinomlar kullanılarak tanımlanan bikübik eğriler oldukça doğal bir şekilde ortaya çıkıyor. Bu tür spline'larla çalışmak çok daha büyük miktarda hesaplama gerektirir. Ama doğru organize süreç sürekli büyüyen fırsatları dikkate almamıza olanak tanıyacak bilgisayar Teknolojisi V maksimum derece. Spline fonksiyonları Segmente izin verin, yani Açıklama. a^ sayılarının indeksi (t) bunu gösterir. Her kısmi D parçası üzerindeki 5(x) fonksiyonunu belirleyen katsayılar kümesinin farklı olduğu. D1 bölümlerinin her birinde, spline 5(x), p dereceli bir polinomdur ve bu bölüm üzerinde p + 1 katsayısı ile belirlenir. Toplam kısmi segmentler - o zaman. Bu, spline'ı tam olarak belirlemek için (p + 1) ve sayıları bulmak gerektiği anlamına gelir. Koşul), 5(x) fonksiyonunun ve türevlerinin w ızgarasının tüm iç düğümlerinde sürekliliği anlamına gelir. Bu tür düğümlerin sayısı m - 1'dir. Böylece tüm polinomların katsayılarını bulmak için p(m - 1) koşulları (denklemler) elde edilir. İçin tam çözünürlüklü spline eksik (koşullar (denklemler). Ek koşulların seçimi, söz konusu problemin doğasına ve bazen de sadece kullanıcının isteğine göre belirlenir. SPLINE TEORİSİ çözüm örnekleri İnterpolasyon ve yumuşatma problemleri çoğunlukla, şu durumlarda dikkate alınır: B düzlemi enterpolasyon problemlerinde belirli bir nokta dizisinden bir veya başka bir spline oluşturmak için gerekli olan spline grafiğinin, katsayılarına m + 1 ek koşullar (denklemler) uygulayan noktalardan geçmesi gerekir. Geri kalan p - 1 koşulları (denklemler). spline'ın kesin yapısı için çoğunlukla, söz konusu segmentin uçlarındaki spline'ın alt türevlerinin değerleri şeklinde belirtilir [. a, 6] - sınır (sınır) koşulları seçme yeteneği. farklı sınır koşulları, çeşitli özelliklere sahip spline'lar oluşturmanıza olanak tanır. Düzgünleştirme problemlerinde spline, grafiği (i" "Y"), * = 0, 1,..., t, noktalarının yakınından geçecek şekilde oluşturulur. ve onlar aracılığıyla değil. Bu yakınlığın ölçüsü farklı şekillerde tanımlanabilir, bu da önemli çeşitlilikte düzleştirme eğrilerine yol açar. Spline fonksiyonlarını oluştururken seçim yapmak için açıklanan seçenekler, tüm çeşitliliklerini tüketmez. Başlangıçta yalnızca parçalı polinom spline fonksiyonları dikkate alındıysa da, uygulamalarının kapsamı genişledikçe, diğer temel fonksiyonlardan "birbirine yapıştırılmış" spline'lar ortaya çıkmaya başladı. İnterpolasyon kübik eğrileri İnterpolasyon probleminin açıklaması [a, 6) parçası üzerinde bir w ızgarası verilsin. Bir dizi sayıyı düşünün. Grid düğümlerinde verilen değerleri alan (a, 6) segmenti üzerinde pürüzsüz bir fonksiyon oluşturun, yani Not: Formüle edilen enterpolasyon problemi, pürüzsüz fonksiyon, bir tabloda verilmiştir (Şekil 2). Böyle bir sorunun pek çok sorunu olduğu açıktır. çeşitli çözümler. Oluşturulmuş bir fonksiyonun üzerine bindirme ek koşullar gerekli netlik sağlanabilir. Uygulamalarda genellikle analitik olarak verilen bir fonksiyona, önceden belirlenmiş yeterli değere sahip bir fonksiyonu kullanarak yaklaşma ihtiyacı vardır. iyi özellikler. Örneğin, belirli bir fonksiyon /(x)'in [a, 6] bölümünün noktalarındaki değerlerinin hesaplanmasının önemli zorluklarla ilişkili olduğu ve/veya verilen fonksiyon /(x)'in gerekli düzgünlüğe sahip olmadığı durumlarda belirli bir işleve sahip olacak ve onun belirtilen dezavantajlarından yoksun olacak, oldukça iyi bir şekilde yaklaşan başka bir işlevin kullanılması uygundur. Fonksiyon enterpolasyonu sorunu. [a, 6] aralığı üzerinde w ızgara düğümlerinde çakışan bir düzgün a(x) fonksiyonu oluşturun: Verilen fonksiyon/(X). Enterpolasyonlu kübik spline'ın tanımı Bir w ağı üzerindeki enterpolasyonlu kübik spline S(x), 1) bölümlerin her birinde üçüncü dereceden bir polinom olan, 2) [a, b] bölümünde iki kez sürekli türevlenebilir olan bir fonksiyondur. ], yani C2[ a, 6] sınıfına aittir ve 3) koşulları karşılar. Segmentlerin her birinde, S(x) spline üçüncü dereceden bir polinomdur ve bu segment üzerinde dört katsayı ile belirlenir. . Toplam parça sayısı m'dir. Bu, spline'ı tam olarak tanımlamak için 4m'lik sayıların bulunması gerektiği anlamına gelir. Koşul, S(x) fonksiyonunun ve onun türevlerinin S"(x) ve 5" sürekliliği anlamına gelir. (x) tüm dahili ızgara düğümlerinde w. Bu tür düğümlerin sayısı m - 1'dir. Böylece tüm polinomların katsayılarını bulmak için başka bir 3(m - 1) koşulu (denklemler) elde edilir. Koşul (2) ile birlikte koşullar (denklemler) elde edilir. Sınır (kenar) koşulları İki eksik koşul, [a, 6] aralığının uçlarındaki spline ve/veya türevlerinin değerleri üzerindeki kısıtlamalar şeklinde belirtilir. Enterpolasyonlu bir kübik spline oluştururken en sık aşağıdaki dört tip sınır koşulu kullanılır. A. 1. tip sınır koşulları. - [a, b] aralığının sonlarında istenen fonksiyonun birinci türevinin değerleri belirtilir. B. 2. tip sınır koşulları. - (a, 6) aralığının sonlarında istenen fonksiyonun ikinci türevinin değerleri belirtilir. B. 3. tip sınır koşulları. periyodik denir. Enterpolasyonlu fonksiyonun T = b-a periyodu ile periyodik olduğu durumlarda bu koşulların yerine getirilmesinin gerekli olması doğaldır. D. 4. tip sınır koşulları. özel yorum gerektirir. Bir yorum. Dahili sepsi düğümlerinde, genel anlamda S(x) fonksiyonunun üçüncü türevi süreksizdir. Ancak üçüncü türevin süreksizliklerinin sayısı 4. tip koşullar kullanılarak azaltılabilir. Bu durumda oluşturulan spline aralıklarla üç kez sürekli türevlenebilir olacaktır. İnterpolasyonlu kübik spline'ın oluşturulması Belirlenecek büyüklüklerin sayısının eşit olduğu bir kübik spline'ın katsayılarını hesaplamak için bir yöntem tanımlayalım. Aralıkların her birinde, spline enterpolasyon fonksiyonu aşağıdaki formda aranır. Burada SPLINE TEORİSİ çözüm ve sayı örnekleri, doğrusal bir sistemin çözümleridir. cebirsel denklemlerşekli sınır koşullarının türüne bağlıdır. Tip 1 ve 2 sınır koşulları için bu sistem aşağıdaki forma sahiptir; burada Katsayılar sınır koşullarının seçimine bağlıdır. 1. tip sınır koşulları: 2. tip sınır koşulları: 3. tip sınır koşulları durumunda sayıları belirleme sistemi şu şekilde yazılır: Bilinmeyenlerin sayısı son sistem periyodiklik koşullarından po = nm çıktığı için mn'ye eşittir. 4. tip sınır koşulları için sayıları belirleme sistemi şu şekildedir: Sistemde bulunan çözüme göre po ve n sayıları formüller kullanılarak belirlenebilir. Her üç doğrusalın matrisleri cebirsel sistemlerçapraz olarak baskın matrislerdir. Matrisler tekil değildir ve bu nedenle bu sistemlerin her birinin benzersiz bir çözümü vardır. Teorem. Koşulları (2) ve yukarıda listelenen dört türden birinin sınır koşulunu karşılayan bir enterpolasyonlu kübik spline mevcuttur ve benzersizdir. Dolayısıyla, enterpolasyonlu bir kübik spline oluşturmak, onun katsayılarını bulmak anlamına gelir. Spline katsayıları bulunduğunda, S(x) spline'ının değeri. keyfi nokta[a, b] segmenti formül (3)'te bulunabilir. Ancak pratik hesaplamalar için daha uygundur. sonraki algoritma 5(g) değerini bulma. x 6 [x" olsun. Önce A ve B değerleri formüller kullanılarak hesaplanır ve ardından 5(x) değeri bulunur: Bu algoritmanın kullanılması, değerin belirlenmesindeki hesaplama maliyetlerini önemli ölçüde azaltır. kullanıcı Sınır (kenar) koşullarının ve enterpolasyon düğümlerinin seçimi, bir ölçüde enterpolasyon spline'larının özelliklerini kontrol edin. A. Sınır (kenar) koşullarının seçimi. Sınır koşullarının seçimi aşağıdakilerden biridir: merkezi sorunlar fonksiyonları enterpolasyon yaparken. Segmentin [a, 6) uçlarına yakın spline 5(g) ile f(x) fonksiyonunun yüksek düzeyde yakınlaştırılmasının sağlanmasının gerekli olduğu durumda özellikle önem kazanmaktadır. Sınır değerleri, spline 5(g)'nin a ve b noktaları yakınındaki davranışı üzerinde gözle görülür bir etkiye sahiptir ve bu etki onlardan uzaklaştıkça hızla zayıflar. Sınır koşullarının seçimi genellikle mevcut duruma göre belirlenir. Ek Bilgiler f(x) yaklaştırılan fonksiyonunun davranışı üzerine. Eğer birinci türevin değerleri f"(x) segmentin uçlarında biliniyorsa (a, 6), o zaman 1. tipin sınır koşullarının kullanılması doğaldır. İkinci türevin değerleri ise f"(x) [a, 6] doğru parçasının uçlarında biliniyorsa, bu tip 2'nin doğal kullanım sınır koşullarıdır. Tip 1 ve 2'nin sınır koşulları arasında bir seçim yapılması durumunda, tip 1'in koşulları tercih edilmelidir. Eğer f(x) - periyodik fonksiyon o zaman 3. tipin sınır koşullarında durmalıyız. olmaması durumunda Ek Bilgiler Yaklaşık fonksiyonun davranışı hakkında hiçbir bilgi yoktur; doğal sınır koşulları olarak adlandırılan koşullar sıklıkla kullanılır. Bununla birlikte, böyle bir sınır koşulu seçimiyle f(x) fonksiyonunun yaklaşımının doğruluğu akılda tutulmalıdır. ) spline tarafından S(x) segmentin uçlarına yakın (a, ft] keskin bir şekilde azalır. Bazen 1. veya 2. tipin sınır koşulları kullanılır, ancak kesin değerler karşılık gelen türevler ve bunların fark yaklaşımları. Bu yaklaşımın doğruluğu düşüktür. Hesaplamalardaki pratik deneyim, söz konusu durumda en uygun olanın 4. tip sınır koşullarının seçimi olduğunu göstermektedir. B. Enterpolasyon düğümlerinin seçimi. Fonksiyonun üçüncü türevi f""(x), [a, b] bölümünün bazı noktalarında süreksizliğe sahipse, o zaman yaklaşımın kalitesini iyileştirmek için bu noktaların enterpolasyon düğümlerinin sayısına dahil edilmesi gerekir. İkinci türev /"(x) süreksizse, süreksizlik noktaları yakınında spline'ın salınımını önlemek için özel önlemler almak gerekir. Tipik olarak enterpolasyon düğümleri, ikinci türevin süreksizlik noktaları düşecek şekilde seçilir. a değeri sayısal bir deney yoluyla seçilebilir (çoğunlukla a = 0,01 ayarlamak yeterlidir). (x) süreksizdir. En basitlerinden biri olarak şunu önerebiliriz: yaklaşım parçasını türevin sürekli olduğu aralıklara bölün ve bu aralıkların her biri üzerinde bir spline oluşturun. Bir enterpolasyon fonksiyonunun seçilmesi (artıları ve eksileri) Yaklaşım 1. Lagrange interpolasyon polinomu Belirli bir dizi için SPLINE TEORİSİ çözüm örnekleri (Şekil 3) enterpolasyon polinomu Lagrange formülle belirlenir. Lagrange enterpolasyon polinomunun özelliklerinin iki zıt konumdan dikkate alınması, ana avantajların dezavantajlardan ayrı olarak tartışılması tavsiye edilir. 1. yaklaşımın temel avantajları: 1) Lagrange enterpolasyon polinomunun grafiği dizinin her noktasından geçer, 2) oluşturulan fonksiyon kolayca tanımlanır (Lagrange enterpolasyon polinomunun ızgaradaki katsayılarının sayısı belirlenecek şekilde belirlenir) m + 1'e eşit), 3) oluşturulan fonksiyonun herhangi bir mertebeden sürekli türevleri vardır, 4) enterpolasyon polinomu verilen dizi tarafından benzersiz bir şekilde belirlenir. 1. yaklaşımın ana dezavantajları: 1) Lagrange enterpolasyon polinomunun derecesi ızgara düğümlerinin sayısına bağlıdır ve bu sayı ne kadar büyük olursa, enterpolasyon polinomunun derecesi de o kadar yüksek olur ve dolayısıyla o kadar fazla hesaplama gerekir, 2) Dizideki en az bir noktayı değiştirmek, Lagrange enterpolasyon polinomunun katsayılarının tamamen yeniden hesaplanmasını gerektirir, 3) toplama yeni nokta diziye eklenmesi Lagrange enterpolasyon polinomunun derecesini bir arttırır ve aynı zamanda katsayılarının tamamen yeniden hesaplanmasına yol açar, 4) sınırsız ağ iyileştirmesi ile Lagrange enterpolasyon polinomunun derecesi süresiz olarak artar. Lagrange enterpolasyon polinomunun sınırsız ağ iyileştirmeli davranışı genellikle özel dikkat gerektirir. Yorumlar A. Yaklaşım Üzerine sürekli fonksiyon polinom. Bir aralıktaki herhangi bir sürekli (ve daha da düzgün) fonksiyonun, bu aralıkta bir polinomla istenildiği kadar yakınlaştırılabileceği bilinmektedir (Weierstrass, 1885). Bu gerçeği formüller diliyle anlatalım. f(x), [a, 6] aralığında sürekli bir fonksiyon olsun. Bu durumda, herhangi bir e > 0 için, [a, 6] aralığındaki herhangi bir x için eşitsizliğin karşılanacağı şekilde bir Є(x) polinomu vardır (Şekil 4). Fonksiyona yaklaşan, aynı dereceden bile polinomların olduğuna dikkat edin. Belirtilen doğrulukta f(x) sonsuz sayıda vardır. [a, 6] doğru parçası üzerinde bir w ızgarası oluşturalım. Genel anlamda düğümlerinin, Pn(x) polinomunun ve f(x) fonksiyonunun grafiklerinin kesişme noktalarıyla çakışmadığı açıktır (Şekil 5). Bu nedenle, verilen ağ için Pn(x) polinomu enterpolasyon değildir. Sürekli bir fonksiyona bir Jla-gracz enterpolasyon polinomu ile yaklaşıldığında, grafiğinin [a, b bölümünün her noktasında f(x) fonksiyonunun grafiğine yakın olması gerekmez, aynı zamanda f(x) fonksiyonunun grafiğine yakın olması gerekmez, aynı zamanda f(x) fonksiyonundan sapabilir. Bu işlevi istediğiniz kadar kullanın. İki örnek verelim. Örnek 1 (Rung, 1901). [-1, 1] aralığındaki fonksiyon için düğüm sayısında sınırsız bir artış ile limit eşitliği sağlanır (Şekil 6) Örnek 2 (Beristein, 1912). Sürekli fonksiyon /(x) = |x| için tek tip ızgaralar üzerine inşa edilmiş bir Lagrange enterpolasyon polinomları dizisi artan sayıda düğüme sahip bir segmentte m, /(x) fonksiyonuna yönelmez (Şekil 7). Yaklaşım 2. Parçalı doğrusal enterpolasyon Eğer enterpolasyonlu fonksiyonun düzgünlüğü terk edilirse, avantajların sayısı ile dezavantajların sayısı arasındaki oran gözle görülür şekilde ilkine doğru değiştirilebilir. Noktaları (xit y) düz çizgi parçalarıyla sırayla birleştirerek parçalı bir doğrusal fonksiyon oluşturalım (Şekil 8). 2. yaklaşımın ana avantajları: 1) parçalı bir doğrusal fonksiyonun grafiği dizinin her noktasından geçer, 2) oluşturulan fonksiyon kolayca tanımlanır (karşılık gelen katsayıların sayısı belirlenecektir) doğrusal fonksiyonlarızgara için (1) 2m'ye eşittir), 3) dizi göz önüne alındığında, oluşturulan fonksiyon benzersiz bir şekilde tanımlanır, 4) enterpolasyon fonksiyonunu tanımlamak için kullanılan polinomların derecesi ızgara düğümlerinin sayısına bağlı değildir (eşittir) 1), 5) Dizideki bir noktanın değiştirilmesi dört sayının hesaplanmasını gerektirir (yeni bir noktadan çıkan iki düz bağlantının katsayıları), 6) toplama ek puan diziye eklenmesi dört katsayının hesaplanmasını gerektirir. Parçalı doğrusal fonksiyon, ağı iyileştirirken de oldukça iyi davranır. 2. yaklaşımın ana dezavantajı: parçalı doğrusal fonksiyonun yaklaşımı düzgün değildir: birinci türevler ızgara düğümlerinde (enterpolasyon kulakları) bir süreksizlik sorunu yaşar. 3'e yaklaşın. Spline enterpolasyonu Önerilen yaklaşımlar, her iki yaklaşımın listelenen avantajlarının sayısı korunurken aynı zamanda dezavantajların sayısı azaltılacak şekilde birleştirilebilir. Bu, p dereceli düzgün bir enterpolasyon spline fonksiyonu oluşturularak yapılabilir. 3. yaklaşımın temel avantajları: 1) oluşturulan fonksiyonun grafiği dizinin her noktasından geçer, 2) oluşturulan fonksiyonun tanımlanması nispeten kolaydır (karşılık gelen polinomların katsayılarının sayısı ızgara için belirlenecektir ( 1) eşittir 3) oluşturulan fonksiyon verilen dizi tarafından benzersiz bir şekilde tanımlanır, 4) derece polinomları ızgara düğümlerinin sayısına bağlı değildir ve bu nedenle arttıkça değişmez, 5) oluşturulan fonksiyon süreklidir p - 1 dahil mertebesine kadar türevler, 6) oluşturulan fonksiyon iyi yaklaşım özelliklerine sahiptir. Kısa bilgi. Önerilen isim - spline - tesadüfi değildir - tanıttığımız düzgün parçalı polinom fonksiyonları ve spline çizimi yakından ilişkilidir. (x, y) düzleminde yer alan dizinin referans noktalarından geçen esnek ideal incelikte bir cetveli ele alalım. Bernoulli-Euler yasasına göre, eğri bir cetvelin doğrusallaştırılmış denklemi şu şekle sahiptir: S(x) bükülmeyi, M(x) destekten desteğe doğrusal olarak değişen bükülme momentini, E1 cetvelin sertliğini gösterir. . Formül çizgilerini tanımlayan S(x) fonksiyonu, dizinin (desteklerin) her biri ve iki bitişik noktası arasındaki üçüncü dereceden bir polinomdur ve tüm aralık (a, 6) boyunca sürekli olarak iki kez türevlenebilir. Bir yorum. 06 sürekli bir fonksiyonun enterpolasyonunu yapmak Lagrange enterpolasyon polinomlarından farklı olarak, tekdüze bir ağ üzerindeki enterpolasyonlu kübik spline dizisi her zaman enterpolasyonlu sürekli fonksiyona yakınsar ve bu fonksiyonun diferansiyel özellikleri geliştikçe yakınsama hızı artar. Örnek. Bir fonksiyon için, düğüm sayısı m = 6 olan bir ızgara üzerindeki kübik bir spline, enterpolasyon polinomu Ls(z) ile aynı dereceden bir yaklaşım hatası verir ve düğüm sayısı m = 21 olan bir ızgara üzerinde bu hata şöyledir: o kadar küçüktür ki, sıradan bir kitap çizimi ölçeğinde gösterilmesi imkansızdır (Şekil 10) (interpolasyon polinomu 1>2o(r), bu durumda yaklaşık 10.000 J'lik bir hata verir). İnterpolasyonlu kübik spline'ın özellikleri A. Kübik spline'ın alproximation özellikleri. Enterpolasyon spline'ının yaklaşım özellikleri, f(x) fonksiyonunun düzgünlüğüne bağlıdır - enterpolasyonlu fonksiyonun düzgünlüğü ne kadar yüksek olursa, yaklaşım sırası da o kadar yüksek olur ve ağ iyileştirildiğinde yakınsama hızı da o kadar yüksek olur. Eğer enterpolasyonlu f(x) fonksiyonu aralıkta sürekli ise Eğer enterpolasyonlu f(x) fonksiyonu [a, 6] aralığında sürekli bir birinci türeve sahipse, yani enterpolasyon spline'ı, 1. veya 3. tip sınır koşullarını karşılıyorsa, o zaman h O için elimizde olur. Bu durumda, sadece spline enterpolasyonlu fonksiyona yakınsamaz, aynı zamanda spline'ın türevi de bu fonksiyonun türevine yakınsar. Spline S(x), [a, b] segmentindeki f(x) fonksiyonuna yaklaşıyorsa ve bunun birinci ve ikinci türevleri sırasıyla bir kübik spline'ın ekstremal özelliğidir. Enterpolasyonlu kübik spline'ın bir tane daha var kullanışlı özellik. Aşağıdaki örneği düşünün. örnek. Grafikleri dizinin noktalarından geçen C2 uzayından bir fonksiyon sınıfının fonksiyonelini en aza indiren bir /(x) fonksiyonu oluşturun. (x;, /(x,) referans noktalarından geçen tüm fonksiyonlar arasında. )) ve belirtilen uzaya ait olan, sınır koşullarını karşılayan kübik spline 5( x), fonksiyonele bir ekstremum (minimum) verir. Açıklama 1. Genellikle bu ekstrem özellik, enterpolasyonlu kübik tanımı olarak alınır. spline. Açıklama 2. Enterpolasyonlu kübik spline'ın yukarıda çok geniş bir fonksiyon sınıfında, yani |o, 5] sınıfında açıklanan ekstremal özelliğe sahip olduğunu belirtmek ilginçtir. 1.2. Kübik spline'ları yumuşatma Yumuşatma probleminin formülasyonu hakkında Bir ızgara ve bir dizi sayı verilsin İlk veriler hakkında yorum Pratikte, dizideki y değerlerinin bazılarıyla belirtildiği durumla sıklıkla uğraşmak gerekir. hata. Aslında bu, her biri için bir aralığın belirlendiği ve bu aralıktaki herhangi bir sayının y değeri olarak alınabileceği anlamına gelir. Örneğin, y'nin değerlerini, bazı y(x) fonksiyonlarının ölçümlerinin sonuçları olarak yorumlamak uygundur. verilen değerler rastgele hata içeren x değişkenleri. Bir işlevi bu tür "deneysel" değerlerden geri yükleme problemini çözerken, enterpolasyonun kullanılması pek tavsiye edilmez, çünkü enterpolasyon işlevi dizideki rastgele bir bileşenin (y,) neden olduğu tuhaf salınımları itaatkar bir şekilde yeniden üretecektir. Daha doğal bir yaklaşım, ölçüm sonuçlarındaki rastgelelik unsurunu bir şekilde azaltmak için tasarlanmış bir yumuşatma prosedürüne dayanmaktadır. Genellikle bu tür problemlerde x = x, * = 0, 1,... m değerleri uygun aralıklara girecek ve buna ek olarak oldukça iyi özelliklere sahip olacak bir fonksiyonun bulunması gerekir. Örneğin sürekli birinci ve ikinci türevleri olur ya da grafiği çok kuvvetli kavisli olmaz, yani kuvvetli salınımlara sahip olmaz. Bu tür bir sorun, belirli bir (tam olarak) dizi verildiğinde, belirli noktalardan geçmeyen, ancak bu noktaların yakınından geçen ve dahası oldukça düzgün bir şekilde değişen bir fonksiyon oluşturmak gerektiğinde de ortaya çıkar. Başka bir deyişle, gerekli işlev verilen diziyi enterpolasyon yapmak yerine yumuşatıyor gibi görünüyordu. Bir w ızgarası ve iki sayı kümesi verilsin. SPLINE TEORİSİ Problemin çözüm örnekleri. Izgara düğümlerindeki değerleri, verilen değerlere göre y sayılarından farklı olan [a, A] segmenti üzerinde düzgün bir fonksiyon oluşturun. Formüle edilen yumuşatma problemi restorasyon bir tabloda belirtilen pürüzsüz fonksiyon. Böyle bir sorunun birçok farklı çözümü olduğu açıktır. Oluşturulan fonksiyona ek koşullar uygulanarak gerekli netlik sağlanabilir. Düzleştirici bir kübik spline'ın tanımı Bir w ızgarası üzerindeki yumuşatıcı kübik spline S(x), 1) bölümlerin her birinde üçüncü dereceden bir polinom olan, 2) [a, 6] bölümünde iki kez sürekli türevlenebilir olan bir fonksiyondur. ], yani C2 sınıfına aittir [a , b], 3) fonksiyonelin minimumunu sağlar burada - verilen sayılar, 4) aşağıda belirtilen üç türden birinin sınır koşullarını karşılar. Sınır (kenar) koşulları Sınır koşulları, w ızgarasının sınır düğümlerindeki spline ve türevlerinin değerleri üzerindeki kısıtlamalar şeklinde belirtilir. A. Tip 1 sınır koşulları. - [a, b) aralığının sonlarında istenen fonksiyonun birinci türevinin değerleri belirtilir. Tip 2 sınır koşulları. - (a, b] aralığının uçlarındaki istenen fonksiyonun ikinci türevleri sıfıra eşittir. B. 3. tipteki sınır koşulları periyodik olarak adlandırılır. Teorem. Kübik spline S(x), fonksiyonel (4)'ü en aza indiren ve yukarıdaki üç türden birinin sınır koşullarını karşılayan, benzersiz bir şekilde tanımlanmıştır. Tanım. Fonksiyonel J(f)'yi en aza indiren ve i-tipinin sınır koşullarını karşılayan bir kübik spline, i-tipinin yumuşatıcı spline'ı olarak adlandırılır. Bu parçayı dört katsayı ile işaretleyin. Toplam parça sayısı m'dir. Bu, spline'ın tam olarak belirlenmesi için 5(ag) fonksiyonunun sürekliliği anlamına gelir. ızgaranın tüm iç düğümlerindeki türevler o ". Bu tür düğümlerin sayısı m - 1'dir. Böylece tüm polinomların katsayılarını hesaplamak için 3(m - 1) koşulu (denklemler) elde ederiz. Fonksiyon, denklemde aranır. Aşağıdaki form ve sayılar, formu sınır koşullarının türüne bağlı olan bir doğrusal cebirsel denklem sisteminin çözümüdür. Öncelikle n* değerlerinin nasıl bulunduğunu anlatalım. Tip 1 ve 2'nin sınır koşulları için sistem doğrusal denklemler Hi değerlerini belirlemek için aşağıdaki formda yazılır. bilinen sayılar). Katsayılar sınır koşullarının seçimine bağlıdır. 1. tip sınır koşulları: 2. tip sınır koşulları: 3. tip sınır koşulları durumunda sayıları belirleme sistemi şu şekilde yazılır: ve tüm katsayılar formül (5)'e göre hesaplanır (değerler) k ve m + k indisli değerler eşit kabul edilir: Önemli* not: Sistemlerin matrisleri dejenere değildir ve bu nedenle bu sistemlerin her birinin benzersiz bir çözümü vardır. n, - sayıları bulunursa miktarlar kolaylıkla belirlenir. Periyodik sınır koşulları durumunda, katsayıların seçimi, fonksiyonel (4)'te yer alan p, - ağırlıklandırma katsayılarının seçimidir, geçen spline'ların özelliklerini bir dereceye kadar kontrol etmenizi sağlar. (x^, Vk) noktası boyunca, buna karşılık gelen p\ ağırlıklandırma faktörü sıfıra eşitlenmelidir. Pratik hesaplamalarda en önemli şey pi değerlerinin seçimidir - D'deki hata olsun. y değerinin ölçülmesi. Bu durumda, düzleştirici spline'ın veya koşuluna uymasını gerektirmek doğaldır. En basit durumda, ağırlıklandırma katsayıları pi, örneğin c'nin yeterince küçük bir sabit olduğu formda belirtilebilir. Ancak bu ağırlık seçimi p, y, - değerlerindeki hatalar nedeniyle “koridor” kullanımına izin vermez. P değerlerini belirlemek için daha rasyonel ama aynı zamanda daha emek yoğun bir algoritma şu şekilde görünebilir. Değerler fc-th yinelemesinde bulunursa, e'nin bilgisayarın bit ızgarası, D değerleri ve doğruluğu dikkate alınarak deneysel olarak seçilen küçük bir sayı olduğu varsayılır. Lineer cebirsel denklem sistemlerinin çözümü. Eğer i noktasındaki fc-th yinelemesinde koşul (6) ihlal edilirse, son formül karşılık gelen ağırlık katsayısı p,'de bir azalma sağlayacaktır. Eğer o zaman bir sonraki yinelemede p'deki bir artış daha fazlasına yol açarsa tam kullanım “koridor” (6) ve sonuçta daha düzgün değişen bir spline. Küçük bir teori A. İnterpolasyon kübik spline'ın katsayılarını hesaplamak için formüllerin gerekçesi. m'nin şu anda bilinmeyen büyüklükler olduğu gösterimi tanıtalım. Sayıları m+1'e eşittir. Enterpolasyon şartlarını sağlayan ve tüm aralıkta sürekli olan [a, b\: formülüne koyarak sırasıyla bir spline elde ederiz. [a, 6] aralığında sürekli birinci türev: (7) ilişkisinin türevini alıp koyarak, karşılık gelen değeri elde ederiz Aslında. M sayılarının, spline fonksiyonunun (7) [a, 6] aralığında sürekli bir ikinci türevi olacak şekilde seçilebileceğini gösterelim. Spline'ın aralıktaki ikinci türevini hesaplayalım: x, - 0 noktasında (t = 1'de) Spline'ın aralıktaki ikinci türevini hesaplayalım. Elimizdeki noktada Spline'ın süreklilik koşulundan a ızgarasının iç düğümlerindeki ikinci türev; m - 1 ilişkisini elde ederiz; bu m - 1 denklemlerine, sınır koşullarından çıkan iki tane daha ekleyerek, m + I bilinmeyen miy i = 0, 1... olan bir m + 1 doğrusal cebirsel denklem sistemi elde ederiz. M. 1. ve 2. tip sınır koşulları durumunda rsh değerlerini hesaplamak için denklem sistemi, (1. tip sınır koşulları), (2. tip sınır koşulları) şeklindedir. Periyodik sınır koşulları için (3. tip sınır koşulları), ağ o; bir düğüm daha uzatın ve varsayın. O zaman σ* değerlerini belirleyen sistem, ikinci ve (th - !)-th grid düğümlerinde form sürekliliğine sahip olacaktır. Son iki bağıntıdan 4. türün sınır koşullarına karşılık gelen eksik iki denklemi elde ederiz: Bilinmeyen goo'yu denklemlerden ve bilinmeyen pc'yi denklemlerden hariç tutarak bir denklem sistemi elde ederiz. Bu sistemdeki bilinmeyenlerin sayısının - I olduğuna dikkat edin. 6. Düzleştirici bir subichess spline'ın verimliliğini hesaplamak için formüllerin gerekçesi. Zi ve nj'nin şu anda bilinmeyen büyüklükler olduğu gösterimi tanıtalım. Sayıları 2m + 2'dir. Formda yazılan spline fonksiyonu tüm (a, 6] aralığı boyunca süreklidir: bu formülü koyarak sırasıyla elde ederiz. z ve n sayılarının, ( 8) formunda yazılan spline'ın [a, 6] aralığında sürekli bir birinci türevi olacak şekilde seçilelim. S(x) spline'ının aralıktaki ilk türevini hesaplayalım: x noktasında. ^ - 0 (t = 1'de) elimizdeki Spline 5(x)'in ilk türevini aralıkta hesaplayalım: Elimizdeki noktada Spline'ın ilk türevinin iç düğümlerdeki süreklilik koşulundan ağ ve --> m - 1 ilişkisini elde ederiz. Bu ilişki uygun bir şekilde matris biçiminde yazılır. Ayrıca, [a, 6) aralığındaki spline'ın türev alınarak sürekli bir ikinci türevi kullanılır. (8) ilişkisini koyarak sırasıyla matris ilişkisini fonksiyonelin (4) minimumu koşulundan elde ederiz. Son iki matris eşitliği, 2m + 2 bilinmeyen için 2m + 2 doğrusal cebirsel denklemden oluşan doğrusal bir sistem olarak düşünülebilir. İlk eşitlikteki r sütununu (9) ilişkisinden elde edilen ifadeyle değiştirerek SPLINE TEORİSİ matris denklemine M sütununu belirlemek için çözüm örneklerine ulaşırız. A + 6HRH7 matrisinin olması nedeniyle bu denklemin benzersiz bir çözümü vardır. her zaman dejenere değildir. Onu bulduktan sonra Eamsshine şehrini kolaylıkla tanımlayabiliriz. A ve H threadmagolal matrislerinin elemanları yalnızca ızgara parametreleriyle ve (hi adımlarıyla) belirlenir ve y^ değerlerine bağlı değildir. Kübik spline fonksiyonlarının doğrusal uzayı Ağ wcra+l düğümü boyunca [a, 6) segmenti üzerinde oluşturulan kübik spline kümesi şu şekildedir: doğrusal uzay m + 3 boyutları: 1) u> ağı üzerinde oluşturulan iki kübik spline'ın toplamı ve u> ağı üzerinde oluşturulan kübik spline'ın çarpımı, Rasgele sayı daha gizli olarak, bunlar bu ızgara üzerinde inşa edilmiş kübik spline'lardır, 2) ızgara üzerinde ve bir düğümden inşa edilen herhangi bir kübik spline, tamamen bu düğümlerdeki y" değerlerinin m + 1 değeri ile belirlenir ve iki sınır şartları- sadece +3 parametre. M + 3 doğrusal bağımsız spline'dan oluşan bu uzayda bir taban seçerek, keyfi bir kübik spline a(x)'i bunların doğrusal birleşimi olarak benzersiz bir şekilde yazabiliriz. Yorum. Bu tür spline ataması hesaplama uygulamalarında yaygındır. Kübik B-spline'lardan (temel veya temel spline'lar) oluşan bir veritabanı özellikle kullanışlıdır. D-spline'ların kullanımı bilgisayar belleği gereksinimlerini önemli ölçüde azaltabilir. L-spline'lar. W ızgarası boyunca sayı doğrusu üzerinde oluşturulan sıfır dereceli bir B-spline'a, u ızgarası boyunca sayı doğrusu üzerinde oluşturulan, k ^ I dereceli B-spline, tekrarlayan fonksiyon aracılığıyla belirlenir. formül Birinci B, -1 "(g) ve ikinci \7\x) derecedeki B-spline grafikleri sırasıyla Şekil 11 ve 12'de gösterilmektedir. İsteğe göre k derecesine sahip bir B-spline sıfırdan farklı olabilir yalnızca belirli bir segmentte (k + 2 düğüm ile tanımlanır) B, -3* (i), y, -+2] segmentinde sıfırdan farklıydı. tekdüze bir ağ durumunda (A adımıyla). Diğer durumlarda tipik bir grafiğimiz vardır. kübik B-splineŞekil 2'de gösterilmiştir. 13. Krediler*. a) fonksiyonu bir aralıkta sürekli iki kez türevlenebilir, yani C2[a, "), k sınıfına aittir, k b) yalnızca ardışık dört aralıkta sıfırdan farklıdır (w ızgarasını tamamen keyfi olarak alınan yardımcı düğümlerle tamamlayalım) Genişletilmiş w* ızgarasını kullanarak m + 3 kübik B-spline'lardan oluşan bir aile oluşturabiliriz: Bu aile, (a, b) segmentindeki kübik spline'ların uzayında bir temel oluşturur. Böylece, keyfi bir kübik spline S(z) olur. ) |b, 6] ızgarası o; iz+1 düğümleri üzerinde inşa edilmiş olup, bu parça üzerinde doğrusal bir kombinasyon şeklinde temsil edilebilmektedir. Problemin koşulları, bu genişlemenin ft katsayılarını benzersiz bir şekilde belirlemektedir. fonksiyonun ızgara düğümlerindeki y* değerlerinin ve fonksiyonun birinci türevinin y o ve Vm değerlerinin ağın uçlarında verildiği durum" (sorun). birincinin sınır koşullarıyla enterpolasyonlar tür), bu katsayılar aşağıdaki formdaki bir sistemden hesaplanır. Hariç tutulduktan sonra miktarlar b-i ve &m+i, bilinmeyenleri 5q, ..., bm olan doğrusal bir sistem ve üç boyutlu bir matris elde ederiz. Bu durum çapraz hakimiyeti ve dolayısıyla bunu çözmek için tarama yöntemini kullanma olasılığını sağlar. 3MMCHMY 1. Doğrusal sistemler Diğer enterpolasyon problemleri dikkate alındığında da benzer türler ortaya çıkar. Zmmchnm* 2. Bölüm 1.1'de açıklanan algoritmalarla karşılaştırıldığında, * enterpolasyon problemlerinde R-spline kullanımı, depolanan bilgi miktarını azaltmamıza*, yani bilgisayar belleği gereksinimlerini önemli ölçüde azaltmamıza olanak sağlar, ancak bu durum yol açsa da operasyon sayısında artış bekleniyor. Spline fonksiyonlarını kullanarak spline eğrilerinin oluşturulması Yukarıda, apsisleri kesin olarak artan bir dizi oluşturacak şekilde noktaları numaralandırılmış dizileri ele aldık. Örneğin, Şekil 2'de gösterilen durum. 14 ne zaman farklı noktalar birbirinin aynısı apsis dizisine izin verilmedi. Bu durum, hem yaklaşım eğrileri sınıfının (trafik fonksiyonları) seçimini hem de bunların yapım yöntemini belirledi. Bununla birlikte, yukarıda önerilen yöntem, dizi noktalarının numaralandırılması ve bunların düzlemdeki konumları kural olarak ilişkili olmadığında, daha genel durumda bir enterpolasyon eğrisinin oldukça başarılı bir şekilde oluşturulmasını mümkün kılar (Şekil 15). Ayrıca, bir enterpolasyon eğrisi oluşturma görevini belirlerken, verilen dizinin düzlemsel olmadığını düşünebiliriz, yani bunu çözmenin gerektiği açıktır. ortak görev kapalı eğriler, kendi kesişim noktalarına sahip eğriler ve uzaysal eğriler dahil olmak üzere kabul edilebilir eğriler sınıfının önemli ölçüde genişletilmesi gerekmektedir. Bu tür eğrileri aşağıdakileri kullanarak tanımlamak uygundur: parametrik denklemler Bunu talep edeceğiz. ek olarak fonksiyonlar yeterli düzgünlüğe sahip olmalıdır; örneğin C1 [a, /0] sınıfına veya C1 sınıfına ait olmalıdırlar. Dizinin tüm noktalarından sırayla geçen bir eğrinin parametrik denklemlerini bulmak için aşağıdaki şekilde ilerleyin. 1. adım. Rastgele bir segmentte)