Artikel

1.2: Naiv - Mathematik


Lassen Sie uns zunächst informell über mathematische Strukturen und mathematische Sprachen sprechen.

Zweifellos haben Sie in mehreren vorangegangenen Mathematikkursen mit mathematischen Modellen gearbeitet, obwohl Sie damals aller Wahrscheinlichkeit nach nicht darauf hingewiesen wurden. Wenn Sie beispielsweise einen Kurs in Linearer Algebra besucht haben, haben Sie einige Erfahrung mit (mathbb{R}^2), (mathbb{R}^3) und (mathbb{R} ^n) als Beispiele für Vektorräume. In der High-School-Geometrie haben Sie gelernt, dass die Ebene ein "Modell" von Euklids Axiomen der Geometrie ist. Vielleicht haben Sie eine Klasse in abstrakter Algebra genommen, in der Sie mehrere Beispiele für Gruppen gesehen haben: Die ganzen Zahlen unter Addition, Permutationsgruppen und die Gruppe der invertierbaren (n imes n)-Matrizen mit der Operation der Matrixmultiplikation sind alle Beispiele für examples Gruppen - sie sind "Modelle" der Gruppenaxiome. All dies sind mathematische Modelle oder Strukturen. Unterschiedliche Strukturen werden für unterschiedliche Zwecke verwendet.

Angenommen, wir denken über eine bestimmte mathematische Struktur nach, zum Beispiel (mathbb{R}^3), die Sammlung geordneter Tripel reeller Zahlen. Wenn wir versuchen, eine ebene euklidische Geometrie in (mathbb{R}^3) zu erstellen, scheitern wir kläglich, da (zum Beispiel) das Parallelpostulat in dieser Struktur falsch ist. Wenn wir dagegen lineare Algebra in (mathbb{R}^3) machen wollen, ist alles schön und gut, da wir uns die Punkte von (mathbb{R}^3) vorstellen können. als Vektoren und seien die Skalare reelle Zahlen. Dann sind die Axiome für einen reellen Vektorraum alle wahr, wenn sie in (mathbb{R}^3) interpretiert werden. Wir werden sagen, dass (mathbb{R}^3) ein Modell der Axiome für einen Vektorraum ist, während es kein Modell für Euklids Axiome für die Geometrie ist.

Wie Sie zweifellos bemerkt haben, hat unsere Diskussion zwei verschiedene Arten von Dingen eingeführt, über die Sie sich Sorgen machen müssen. Da sind zunächst die mathematischen Modelle, die man sich als mathematische Welten oder Konstrukte vorstellen kann. Beispiele hierfür sind (mathbb{R}^3), die Sammlung von Polynomen vom Grad 17, die Menge der 3x2-Matrizen und die reelle Gerade. Wir haben auch über die Axiome der Geometrie und Vektorräume gesprochen, und diese sind etwas anderes. Lassen Sie uns diese Axiome für einen Moment diskutieren.

Betrachten wir nur zur Veranschaulichung einige der Axiome, die besagen, dass (V) ein reeller Vektorraum ist. Sie sind hier sowohl informell als auch in einer formelleren Sprache aufgeführt:

Die Vektoraddition ist kommutativ: (left(forall u in V ight) left(forall vin V ight) u + v = v + u).

Es gibt einen Nullvektor: (left(exists 0 in V ight) left(forall vin V ight) v + 0 = v).

Einmal ist alles sich selbst: (left(forall vin V ight) 1v = v).

Machen Sie sich keine Sorgen, wenn Ihnen die formale Sprache zu diesem Zeitpunkt noch nicht vertraut ist; es genügt zu bemerken, dass es ist eine formale Sprache. Aber lassen Sie uns auf ein paar Dinge hinweisen, die Sie wahrscheinlich ohne Frage akzeptiert haben. Das Additionszeichen in den ersten beiden Axiomen ist nicht dasselbe Pluszeichen, das Sie verwendet haben, als Sie in der ersten Klasse das Addieren gelernt haben. Oder besser gesagt, es ist das gleiche Zeichen, aber du interpretieren das Zeichen anders. Wenn der betrachtete Vektorraum (mathbb{R}^3) ist, wissen Sie, dass die Addition, was die ersten beiden Axiome dort oben betrifft, eine Vektoraddition ist. Ebenso ist die 0 im zweiten Axiom nicht die reelle Zahl 0; es ist vielmehr der Nullvektor. Außerdem ist die Multiplikation im dritten Axiom, die durch die Nebeneinanderstellung der 1 und des (v) angezeigt wird, die skalare Multiplikation des Vektorraums, nicht die Multiplikation des dritten Grades.

Es scheint also, dass wir in der Lage sein müssen, einige Symbole in einer bestimmten formalen Sprache zu betrachten und dann diese Symbole zu nehmen und sie in irgendeiner Weise mit einer mathematischen Struktur zu verknüpfen. Unterschiedliche Interpretationen der Symbole führen zu unterschiedlichen Schlussfolgerungen hinsichtlich des Wahrheitsgehalts der formalen Aussage. Nehmen wir zum Beispiel das obige Kommutivitätsaxiom und arbeiten mit dem Raum (V) als (mathbb{R}^3), interpretieren aber das Zeichen (+) als ein Kreuzprodukt anstelle einer Vektoraddition , sehen wir, dass das Axiom nicht mehr gilt, da das Kreuzprodukt nicht kommutativ ist.

Dies sind also unsere nächsten Ziele: formale Sprachen einzuführen, eine offizielle Definition einer mathematischen Struktur zu geben und die Wahrheit in diesen Strukturen zu diskutieren. Schönheit kommt später.


1.2: Naiv - Mathematik

Dozent Dr. Neil Donaldson
Büro RH 472
Sprechzeiten MW 11-12 + 1-2
E-Mail an [email protected]
Vorlesungszeiten MWF 10 Uhr SH 174

Lehrassistent Kai-wei Zhao
Diskussionszeiten MW 9 Uhr HIB 110
Büro/Stunden RH 440V/Di 2-3 + Do 2-4
E-Mail an [email protected]

Kurstext und Lehrplan Der Kurs deckt die Voraussetzungen für ein gründliches Studium der Analysis ab: Wir behandeln Zahlen, Vollständigkeit, Folgen, Beweis, Reihen und stetige Funktionen. Viele dieser Themen wurden in Mathe 2A/B ganz naiv eingeführt und in Mathe 13 angerissen: hier haben wir beweisen alles!

Kurstext Elementaranalyse: Die Theorie der Infinitesimalrechnung von Kenneth Ross
Das Buch ist nicht erforderlich --- Hausaufgabenfragen und -notizen werden getippt und auf der Hausaufgabenseite veröffentlicht --- obwohl das gleiche Buch auch 140B umfasst, wird es empfohlen, wenn Sie an diesem Kurs teilnehmen.
Für einen detaillierteren Lehrplan mit den pro Tag behandelten Abschnitten und Bewertungen klicken Sie hier

    werden die meisten Wochen eingestellt und in der Diskussion gesammelt. Eine Hausaufgabe fällt weg.
  • In Diskussionsklassen werden sechs Quizfragen gestellt. Sie gehen in der Regel von der Kenntnis der in dieser Woche abgegebenen Hausaufgaben aus. Ein Quiz wird fallen gelassen. Hausaufgaben und Quiz finden in der Regel während der Mittwoch Diskussion.
  • Midterm: während der regulären Unterrichtszeit am Freitag, den 1. November
  • Abschlussprüfung: findet am Montag, 9. Dezember, 10:30-12:30 Uhr im üblichen Klassenzimmer statt. Die Prüfung wird umfassend sein.

Im Mathematikunterricht werden Entscheidungen in Bezug auf Wartelisten, Hinzufügungen, Löschungen und bestandene/nicht bestandene Änderungen NICHT von den Kursleitern getroffen. Informationen zur Navigation durch das System finden Sie hier. Im Wesentlichen haben Sie bis zum Ende von Woche 2 Zeit, um alle Adds, Drops und Grade-Änderungen abzuschließen, was alles online erledigt wird.


Das Gesetz der großen Zahlen

Diese Frage basierte auf einer naiven Herangehensweise an das Glücksspiel. Der nächste, aus dem Jahr 2000, basiert auf der Wahrscheinlichkeitstheorie. (Die Fragen wurden in unvollkommenem Englisch gestellt, das ich nach meinem Verständnis neu formulieren werde, um eine Fehlinterpretation in der archivierten Version zu korrigieren. Doktor TWE hat es richtig gemacht.)

Doktor TWE antwortete und behandelte mehrere mögliche Interpretationen von “Ergebnis”:

Wenn ich seine Berechnung überprüfe und damit bestätige, was er meinte, erhalte ich die Wahrscheinlichkeit, mit drei Würfeln mindestens eine Sechs zu würfeln, das Komplement, keine Sechsen zu würfeln: (displaystyle 1 – frac<5^3> <6 ^3>= 42,1%). Beim nächsten Mal werde ich das weiter besprechen.

Doktor TWE bestätigte seine Berechnung und erklärte dann, was dieses Gesetz bedeutet und nicht bedeutet:

Wichtig ist hier, dass die Dinge auf lange Sicht “mittelwert” werden, so dass Sie mindestens eine 6 in 42,1% der Brötchen erhalten, aber nicht, weil zu jedem Zeitpunkt eine größere Chance besteht, sich auszugleichen der Durchschnitt — es passiert nur, weil es sehr lange dauert. Es liegt nicht daran, dass vergangene Ereignisse Auswirkungen auf zukünftige Ereignisse haben und diese mit den “Durchschnitten” in Einklang bringen.

Weitere Informationen zum Gesetz der großen Zahlen finden Sie unter


Mathematik für Topcoder

Ich habe gesehen, wie sich eine Reihe von Konkurrenten beschwert haben, dass sie unfair benachteiligt werden, weil viele Topcoder-Probleme zu mathematisch sind. Persönlich liebe ich Mathematik und bin daher in dieser Frage voreingenommen. Trotzdem bin ich der festen Überzeugung, dass Probleme zumindest etwas Mathematik beinhalten sollten, denn Mathematik und Informatik gehen oft Hand in Hand. Es ist schwer sich eine Welt vorzustellen, in der diese beiden Felder ohne jegliche Interaktion miteinander existieren könnten. Heutzutage wird ein Großteil der angewandten Mathematik auf Computern durchgeführt, wie das Lösen großer Gleichungssysteme und das Nähern von Lösungen für Differentialgleichungen, für die es keine geschlossene Formel gibt. Mathematik ist in der Informatikforschung weit verbreitet und wird auch stark auf Graphalgorithmen und Bereiche der Computer Vision angewendet.

In diesem Artikel werden die Theorie und die praktische Anwendung auf einige der gebräuchlicheren mathematischen Konstrukte erörtert. Die behandelten Themen sind: Primzahlen, GCD, Grundgeometrie, Basen, Brüche und komplexe Zahlen.

Primzahlen

Eine Zahl ist prim, wenn sie nur durch 1 und sich selbst teilbar ist. Zum Beispiel sind 2, 3, 5, 79, 311 und 1931 alle Primzahlen, während 21 keine Primzahl ist, da sie durch 3 und 7 teilbar ist. Um herauszufinden, ob eine Zahl n eine Primzahl ist, können wir einfach prüfen, ob sie irgendwelche Zahlen darunter teilt es. Wir können den Modulus-Operator (%) verwenden, um die Teilbarkeit zu überprüfen:

Wir können diesen Code schneller laufen lassen, indem wir beachten, dass wir nur die Teilbarkeit für Werte von i überprüfen müssen, die kleiner oder gleich der Quadratwurzel von n sind (dies nennen wir m). Wenn n eine Zahl teilt, die größer als m ist, wird das Ergebnis dieser Division eine Zahl kleiner als m sein und somit wird n auch eine Zahl teilen, die kleiner oder gleich m ist. Eine weitere Optimierung besteht darin, zu erkennen, dass es keine geraden Primzahlen größer als 2 gibt. Nachdem wir überprüft haben, dass n nicht gerade ist, können wir den Wert von i sicher um 2 erhöhen :

Angenommen, wir wollten alle Primzahlen von 1 bis 100000 finden, dann müssten wir die obige Methode 100000 Mal aufrufen. Dies wäre sehr ineffizient, da wir die gleichen Berechnungen immer wieder wiederholen würden. In dieser Situation ist es am besten, eine Methode zu verwenden, die als Sieb von Eratosthenes bekannt ist. Das Sieb des Eratosthenes erzeugt alle Primzahlen von 2 bis zu einer gegebenen Zahl n. Es beginnt mit der Annahme, dass alle Zahlen Primzahlen sind. Es nimmt dann die erste Primzahl und entfernt alle ihre Vielfachen. Dann wendet er das gleiche Verfahren auf die nächste Primzahl an. Dies wird so lange fortgesetzt, bis alle Nummern verarbeitet wurden. Betrachten Sie zum Beispiel, Primzahlen im Bereich von 2 bis 20 zu finden. Wir beginnen damit, alle Zahlen aufzuschreiben:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
2 ist die erste Primzahl. Wir streichen nun alle seine Vielfachen durch, also jede zweite Zahl:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Die nächste nicht durchgestrichene Zahl ist 3 und somit die zweite Primzahl. Wir streichen nun alle Vielfachen von 3 durch, also jede dritte Zahl von 3:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Alle verbleibenden Zahlen sind Primzahlen und wir können den Algorithmus sicher beenden. Unten ist der Code für das Sieb:

In der obigen Methode erstellen wir ein boolesches Array prime, das die Primzahl jeder Zahl kleiner gleich n speichert. Wenn prime[i] wahr ist, dann ist Zahl i eine Primzahl. Die äußere Schleife findet die nächste Primzahl, während die innere Schleife alle Vielfachen der aktuellen Primzahl entfernt.

Der größte gemeinsame Teiler (GCD) zweier Zahlen a und b ist die größte Zahl, die sich gleichmäßig in a und b aufteilt. Naiv könnten wir von der kleinsten der beiden Zahlen ausgehen und uns nach unten vorarbeiten, bis wir eine Zahl finden, die sich in beide teilt:

Obwohl diese Methode für die meisten Anwendungen schnell genug ist, gibt es eine schnellere Methode namens Euklid-Algorithmus. Der Algorithmus von Euklid iteriert über die beiden Zahlen, bis ein Rest von 0 gefunden wird. Angenommen, wir möchten die GCD von 2336 und 1314 ermitteln. Wir beginnen damit, die größere Zahl (2336) durch die kleinere Zahl (1314) plus einen Rest auszudrücken:
2336 = 1314 x 1 + 1022
Dasselbe machen wir jetzt mit 1314 und 1022:
1314 = 1022 x 1 + 292
Wir setzen diesen Vorgang fort, bis wir einen Rest von 0 erreichen:
1022 = 292 x 3 + 146
292 = 146 x 2 + 0
Der letzte von Null verschiedene Rest ist der GCD. Die GCD von 2336 und 1314 ist also 146. Dieser Algorithmus kann leicht als rekursive Funktion codiert werden:

Mit diesem Algorithmus können wir das kleinste gemeinsame Vielfache (LCM) zweier Zahlen finden. Zum Beispiel ist der LCM von 6 und 9 18, da 18 die kleinste Zahl ist, die sowohl 6 als auch 9 teilt. Hier ist der Code für die LCM-Methode:

Als letzte Anmerkung kann der Algorithmus von Euklid verwendet werden, um lineare diophantische Gleichungen zu lösen. Diese Gleichungen haben ganzzahlige Koeffizienten und haben die Form:
ax + by = c

Geometrie

Gelegentlich verlangen uns Probleme, den Schnittpunkt von Rechtecken zu finden. Es gibt verschiedene Möglichkeiten, ein Rechteck darzustellen. Für die kartesische Standardebene besteht eine gängige Methode darin, die Koordinaten der unteren linken und oberen rechten Ecke zu speichern.

Angenommen, wir haben zwei Rechtecke R1 und R2. Sei (x1, y1) die Position der unteren linken Ecke von R1 und (x2, y2) die Position ihrer oberen rechten Ecke. In ähnlicher Weise seien (x3, y3) und (x4, y4) die jeweiligen Eckpositionen für R2. Der Schnittpunkt von R1 und R2 ist ein Rechteck R3, dessen untere linke Ecke bei (max(x1, x3), max(y1, y3)) und obere rechte Ecke bei (min(x2, x4), min(y2 , y4)). Falls max(x1, x3) > min(x2, x4) oder max(y1, y3) > min(y2, y4) dann existiert R3 nicht, dh R1 und R2 schneiden sich nicht. Diese Methode kann auf Schnittmengen in mehr als 2 Dimensionen erweitert werden, wie in CuboidJoin (SRM 191, Div 2 Hard) zu sehen ist.

Oft haben wir es mit Polygonen zu tun, deren Scheitel ganzzahlige Koordinaten haben. Solche Polygone werden Gitterpolygone genannt. In seinem Tutorial zu Geometry Concepts präsentiert lbackstrom eine nette Methode, um die Fläche eines Gitterpolygons anhand seiner Scheitelpunkte zu bestimmen. Angenommen, wir kennen die genaue Position der Scheitelpunkte nicht und erhalten stattdessen zwei Werte:
B = Anzahl der Gitterpunkte am Rand des Polygons
I = Anzahl der Gitterpunkte im Inneren des Polygons
Erstaunlicherweise ist die Fläche dieses Polygons dann gegeben durch:
Fläche = B/ 2 + I - 1
Die obige Formel wird nach Georg Alexander Pick (1859 – 1943) als Pick-Theorem bezeichnet. Um zu zeigen, dass der Satz von Pick für alle Gitterpolygone gilt, müssen wir ihn in 4 separaten Teilen beweisen. Im ersten Teil zeigen wir, dass der Satz für jedes Gitterrechteck (mit achsparallelen Seiten) gilt. Da ein rechtwinkliges Dreieck einfach die Hälfte eines Rechtecks ​​ist, ist es nicht allzu schwierig zu zeigen, dass der Satz auch für jedes rechtwinklige Dreieck (mit achsparallelen Seiten) gilt. Der nächste Schritt besteht darin, ein allgemeines Dreieck zu betrachten, das als Rechteck mit einigen rechtwinkligen Dreiecken dargestellt werden kann, die aus seinen Ecken herausgeschnitten sind. Schließlich können wir zeigen, dass, wenn der Satz für zwei beliebige Gitterpolygone gilt, die eine gemeinsame Seite haben, er auch für das Gitterpolygon gilt, das durch Entfernen der gemeinsamen Seite gebildet wird. Wenn wir das vorherige Ergebnis mit der Tatsache kombinieren, dass jedes einfache Polygon eine Vereinigung von Dreiecken ist, erhalten wir die endgültige Version des Satzes von Pick. Der Satz von Pick ist nützlich, wenn wir die Anzahl der Gitterpunkte innerhalb eines großen Polygons finden müssen.

Eine weitere Formel, die man sich merken sollte, ist die Eulersche Formel für polygonale Netze. Ein polygonales Netz ist ein einfaches Polygon, das in kleinere Polygone unterteilt ist. Die kleineren Polygone werden als Flächen bezeichnet, die Seiten der Flächen als Kanten und die Eckpunkte der Flächen als Eckpunkte. Die Eulersche Formel besagt dann:
V - E + F = 2, wobei
V = Anzahl der Scheitelpunkte
E = Anzahl der Kanten
F = Anzahl der Gesichter
Betrachten Sie zum Beispiel ein Quadrat, in dem beide Diagonalen gezeichnet sind. Wir haben V = 5, E = 8 und F = 5 (die Außenseite des Quadrats ist auch eine Fläche) und somit V – E + F = 2.

Wir können mit Induktion zeigen, dass die Eulersche Formel funktioniert. Wir müssen die Induktion mit V = 2 beginnen, da jede Ecke auf mindestens einer Kante liegen muss. Bei V = 2 ist nur ein Polygonnetztyp möglich. Es hat zwei Ecken, die durch eine Anzahl von Kanten E verbunden sind. Dieses polygonale Netz hat E-Flächen (E – 1 „Mitte“ und 1 „Außen“). Also V – E + F = 2 – E + E = 2. Wir nehmen nun an, dass V – E + F = 2 für alle 2<=V<=n gilt. Sei V = n + 1. Wähle eine beliebige Ecke w zufällig. Angenommen, w ist mit dem Rest des Netzes durch G-Kanten verbunden. Wenn wir w und all diese Kanten entfernen, haben wir ein Netz mit n Ecken, E – G Kanten und F – G + 1 Flächen. Nach unserer Annahme haben wir:
( n ) - ( E - G) + ( F - G + 1 ) = 2
also (n+1) - E + F = 2
Wegen V = n + 1 gilt V – E + F = 2. Damit haben wir nach dem mathematischen Induktionsprinzip die Eulersche Formel bewiesen.

Basen

Ein sehr häufiges Problem, mit dem Topcoder-Konkurrenten bei Herausforderungen konfrontiert sind, ist die Konvertierung in und von binären und dezimalen Darstellungen (unter anderem).

Was bedeutet die Basis der Zahl eigentlich? Wir beginnen mit der Arbeit in der Standard- (Dezimal-) Basis. Betrachten Sie die Dezimalzahl 4325. 4325 steht für 5 + 2 x 10 + 3 x 10 x 10 + 4 x 10 x 10 x 10. Beachten Sie, dass der „Wert“ jeder nachfolgenden Ziffer von rechts um den Faktor 10 zunimmt nach links.

Binäre Zahlen funktionieren ähnlich. Sie setzen sich ausschließlich aus 0 und 1 zusammen und der „Wert“ jeder Ziffer erhöht sich von rechts nach links um den Faktor 2. 1011 in binär steht beispielsweise für 1 + 1 x 2 + 0 x 2 x 2 + 1 x 2 x 2 x 2 = 1 + 2 + 8 = 11 in dezimal. Wir haben gerade eine Binärzahl in eine Dezimalzahl umgewandelt. Gleiches gilt für andere Basen. Hier ist Code, der eine Zahl n zur Basis b (2<=b<=10) in eine Dezimalzahl umwandelt:

Java-Benutzer werden sich freuen zu wissen, dass das Obige auch geschrieben werden kann als:
Ganzzahl zurückgeben. parse Int( "" + n , b )
Die Umwandlung von einer Dezimalzahl in eine Binärzahl ist genauso einfach. Angenommen, wir wollten 43 dezimal in binär umwandeln. Bei jedem Schritt der Methode teilen wir 43 durch 2 und merken uns den Rest. Die letzte Restliste ist die erforderliche binäre Darstellung:
43 / 2 = 21 + Rest 1
21 / 2 = 10 + Rest 1
10 / 2 = 5 + Rest 0
5 / 2 = 2 + Rest 1
2 / 2 = 1 + Rest 0
1 / 2 = 0 + Rest 1
43 in Dezimal ist also 101011 in Binär. Indem wir in unserer vorherigen Methode alle Vorkommen von 10 mit b vertauschen, erstellen wir eine Funktion, die eine Dezimalzahl n in eine Zahl zur Basis b (2<=b<=10) umwandelt:

Wenn die Basis b über 10 liegt, müssen wir nicht numerische Zeichen verwenden, um Ziffern mit einem Wert von 10 und mehr darzustellen. Wir können „A“ für 10 stehen lassen, „B“ für 11 stehen und so weiter. Der folgende Code konvertiert von einer Dezimalzahl in eine beliebige Basis (bis zur Basis 20):

In Java gibt es einige nützliche Abkürzungen beim Konvertieren von dezimalen in andere gängige Darstellungen, wie binär (Basis 2), oktal (Basis 8) und hexadezimal (Basis 16):
Ganzzahl . zu BinaryString( n )
Ganzzahl . zu OctalString( n )
Ganzzahl . zu HexString( n )

Brüche und komplexe Zahlen

Bruchzahlen können in vielen Problemen gesehen werden. Der vielleicht schwierigste Aspekt beim Umgang mit Brüchen besteht darin, die richtige Darstellungsweise zu finden. Obwohl es möglich ist, eine Bruchklasse mit den erforderlichen Attributen und Methoden zu erstellen, reicht es für die meisten Zwecke aus, Brüche als 2-Element-Arrays (Paare) darzustellen. Die Idee ist, dass wir den Zähler im ersten Element und den Nenner im zweiten Element speichern. Wir beginnen mit der Multiplikation zweier Brüche a und b:

Das Addieren von Brüchen ist etwas komplizierter, da nur Brüche mit gleichem Nenner addiert werden können. Zuerst müssen wir den gemeinsamen Nenner der beiden Brüche finden und dann durch Multiplikation die Brüche so transformieren, dass sie beide den gemeinsamen Nenner als Nenner haben. Der gemeinsame Nenner ist eine Zahl, die beide Nenner teilen kann und ist einfach die LCM (vorher definiert) der beiden Nenner. Lassen Sie uns zum Beispiel 4/9 und 1/6 hinzufügen. LCM von 9 und 6 ist 18. Um den ersten Bruch zu transformieren, müssen wir ihn mit 2/2 multiplizieren und den zweiten mit 3/3 multiplizieren:
4 / 9 + 1 / 6 = ( 4 * 2 )/( 9 * 2 ) + ( 1 * 3 )/( 6 * 3 ) = 8 / 18 + 3 / 18
Sobald beide Brüche den gleichen Nenner haben, addieren wir einfach die Zähler, um das endgültige Ergebnis von 11/18 zu erhalten. Die Subtraktion ist sehr ähnlich, außer dass wir im letzten Schritt subtrahieren:
4 / 9 - 1 / 6 = 8 / 18 - 3 / 18 = 5 / 18
Hier ist der Code zum Addieren von zwei Brüchen:

Schließlich ist es nützlich zu wissen, wie man einen Bruch auf seine einfachste Form reduziert. Die einfachste Form eines Bruches tritt auf, wenn die GCD von Zähler und Nenner gleich 1 ist. Wir machen das so:

Mit einem ähnlichen Ansatz können wir andere spezielle Zahlen darstellen, wie z. B. komplexe Zahlen. Im Allgemeinen ist eine komplexe Zahl eine Zahl der Form a + ib, wobei a und b reelle Zahlen sind und i die Quadratwurzel von -1 ist. Um zum Beispiel zwei komplexe Zahlen m = a + ib und n = c + id zu addieren, gruppieren wir einfach die gleichen Terme:
m + n
= (a + ib) + (c + id)
= (a + c) + i (b + d)
Die Multiplikation zweier komplexer Zahlen entspricht der Multiplikation zweier reeller Zahlen, außer dass wir die Tatsache verwenden müssen, dass i^2 = -1:
m * nein
= (a + ib) * (c + id)
= ac + iad + ibc + (i^2)bd
= (ac - bd) + i(ad + bc)
Durch Speichern des Realteils im ersten Element und des komplexen Teils im zweiten Element des 2-Element-Arrays können wir Code schreiben, der die obige Multiplikation durchführt:

Fazit

Abschließend möchte ich hinzufügen, dass man nicht an die Spitze der Topcoder-Rangliste aufsteigen kann, ohne die in diesem Artikel skizzierten mathematischen Konstrukte und Algorithmen zu verstehen. Vielleicht eines der häufigsten Themen in mathematischen Problemen ist das Thema Primzahlen. Darauf folgt das Thema Basen, wahrscheinlich weil Computer im Binärformat arbeiten und man daher wissen muss, wie man von Binär in Dezimal umwandelt. Die Konzepte von GCD und LCM sind sowohl in der reinen Mathematik als auch in geometrischen Problemen üblich. Schließlich habe ich das letzte Thema nicht so sehr wegen seiner Nützlichkeit bei Topcoder-Wettbewerben aufgenommen, sondern mehr, weil es ein Mittel zur Behandlung bestimmter Zahlen demonstriert.


Inhalt

Die Determinante wird entweder durch det oder durch die vertikalen Balken um die Matrix gekennzeichnet. Beispielsweise,

Erste Eigenschaften Bearbeiten

Dies gilt ähnlich, wenn die beiden Spalten gleich sind. Außerdem,

Wenn die Matrixeinträge reelle Zahlen sind, kann die Matrix A verwendet werden, um zwei lineare Abbildungen darzustellen: eine, die die Standardbasisvektoren auf die Zeilen von A abbildet, und eine, die sie auf die Spalten von A abbildet. In jedem Fall bilden die Bilder der Basisvektoren ein Parallelogramm, das das Bild des Einheitsquadrats unter der Abbildung darstellt. Das durch die Zeilen der obigen Matrix definierte Parallelogramm ist das mit Scheitelpunkten bei (0, 0) , (ein, b) , (ein + c, b + d) , und (c, d) , wie in der beigefügten Abbildung gezeigt.

Der absolute Wert von Anzeigebc ist die Fläche des Parallelogramms und stellt somit den Skalierungsfaktor dar, mit dem Flächen durch A transformiert werden. (Das von den Spalten von A gebildete Parallelogramm ist im Allgemeinen ein anderes Parallelogramm, aber da die Determinante in Bezug auf Zeilen und Spalten symmetrisch ist, ist die Fläche gleich.)

Der Absolutwert der Determinante wird zusammen mit dem Vorzeichen zu orientierter Bereich des Parallelogramms. Die orientierte Fläche ist die gleiche wie die normale Fläche, außer dass sie negativ ist, wenn sich der Winkel vom ersten zum zweiten Vektor, der das Parallelogramm definiert, im Uhrzeigersinn dreht (was der Richtung entgegengesetzt ist, die man für die Identitätsmatrix erhalten würde).

Zu zeigen, dass Anzeigebc der vorzeichenbehaftete Bereich ist, kann man sich eine Matrix vorstellen, die zwei Vektoren enthält du ≡ (ein, b) und v ≡ (c, d) die Seiten des Parallelogramms darstellen. Der vorzeichenbehaftete Bereich kann als | . ausgedrückt werdendu| |v| Sünde θ für den Winkel θ zwischen den Vektoren, das ist einfach Basis mal Höhe, die Länge eines Vektors mal die senkrechte Komponente des anderen. Aufgrund des Sinus ist dies bereits der vorzeichenbehaftete Bereich, kann jedoch bequemer unter Verwendung des Kosinus des komplementären Winkels zu einem senkrechten Vektor ausgedrückt werden, z. du ⊥ = (−b, ein) , sodass |du ⊥ | |v| cos θ ' , die durch das Muster des Skalarprodukts gleich bestimmt werden kann Anzeigebc :

Somit gibt die Determinante den Skalierungsfaktor und die Orientierung an, die durch die Abbildung induziert wird, dargestellt durch EIN. Wenn die Determinante gleich eins ist, ist die durch die Matrix definierte lineare Abbildung flächengleich und orientierungserhaltend.

Das als bekannte Objekt Bivektor hängt mit diesen Ideen zusammen. In 2D kann es interpretiert werden als ein orientiertes ebenes Segment gebildet, indem man sich zwei Vektoren jeweils mit Ursprung (0, 0) und Koordinaten (ein, b) und (c, d) . Die Bivektorgröße (bezeichnet durch (ein, b) ∧ (c, d) ) ist der signierter Bereich, die auch die Determinante ist Anzeigebc . [2]

Die Determinante gibt das Vorzeichen nein-dimensionales Volumen dieses Parallelotops, det ( A ) = ± vol ( P ) , >(P),> und beschreibt damit allgemeiner die nein-dimensionaler Volumenskalierungsfaktor der linearen Transformation erzeugt durch EIN. [3] (Das Vorzeichen zeigt an, ob die Transformation die Orientierung beibehält oder umkehrt.) Insbesondere wenn die Determinante null ist, dann hat dieses Parallelotop das Volumen null und ist nicht vollständig nein-dimensional, was angibt, dass die Dimension des Bildes von EIN ist weniger als nein. Dies bedeutet, dass EIN erzeugt eine lineare Transformation, die weder auf noch eins-zu-eins ist und daher nicht invertierbar ist.

In der Fortsetzung, EIN ist eine quadratische Matrix mit nein Reihen und nein Spalten, so dass es geschrieben werden kann als

Die Determinante von EIN wird mit det(EIN), oder es kann direkt in den Matrixeinträgen angegeben werden, indem umschließende Striche anstelle von Klammern geschrieben werden:

Es gibt verschiedene äquivalente Möglichkeiten, die Determinante einer quadratischen Matrix zu definieren EIN, also eine mit der gleichen Anzahl von Zeilen und Spalten: Die Determinante kann über die Leibniz-Formel definiert werden, eine explizite Formel, bei der Summen von Produkten bestimmter Einträge der Matrix verwendet werden. Die Determinante kann auch als eindeutige Funktion charakterisiert werden, abhängig von den Einträgen der Matrix, die bestimmte Eigenschaften erfüllen. Dieser Ansatz kann auch verwendet werden, um Determinanten zu berechnen, indem die fraglichen Matrizen vereinfacht werden.

Leibniz-Formel Bearbeiten

Das Leibniz-Formel für die Determinante einer 3 × 3-Matrix lautet:

Die Regel von Sarrus ist eine Gedächtnisstütze für diese Formel: die Summe der Produkte von drei diagonalen Nordwest- bis Südostlinien von Matrixelementen, minus der Summe der Produkte von drei diagonalen Südwest- bis Nordostlinien von Elementen , wenn die Kopien der ersten beiden Spalten der Matrix wie in der Abbildung daneben geschrieben werden:

Dieses Schema zur Berechnung der Determinante einer 3 × 3-Matrix lässt sich nicht in höhere Dimensionen übertragen.

Nein × nein Matrizen Bearbeiten

wird auch kürzer in Pi-Notation geschrieben als

Unter Verwendung dieser Begriffe lautet die Definition der Determinante mit der Leibniz-Formel dann

eine Summe, die alle Permutationen umfasst, wobei jeder Summand ein Produkt von Einträgen der Matrix ist, multipliziert mit einem von der Permutation abhängigen Vorzeichen.

Die Summe der sechs Terme in der dritten Spalte lautet dann

Dies gibt die obige Formel zurück, da das Levi-Civita-Symbol Null ist, wenn die Indizes i 1 , … , i n ,dots ,i_> keine Permutation bilden. [4] [5]

Charakterisierung der Determinante Edit

Die Determinante kann durch die folgenden drei Schlüsseleigenschaften charakterisiert werden. Um diese zu formulieren, betrachtet man bequem eine n × n -Matrix EIN als aus seinen n Spalten zusammengesetzt, so bezeichnet als

  1. det ( I ) = 1 , wobei I eine Identitätsmatrix ist.
  2. Die Determinante ist multilinear: wenn die jSpalte einer Matrix A wird als Linearkombination geschrieben a j = r ⋅ v + w =rcdot v+w> von zwei Spaltenvektorenv und w und eine Zahl r, dann ist die Determinante von EIN ist als ähnliche Linearkombination ausdrückbar: | A | = | a 1 , … , a j − 1 , r ⋅ v + w , a j + 1 , … , a n | = r ⋅ | a 1 , … , v , … a n | + | a 1 , … , w , … , a n | |A|&=<ig |>a_<1>,dots ,a_,rcdot v+w,a_,Punkte,a_|&=rcdot |a_<1>,dots ,v,dots a_|+|a_<1>,dots ,w,dots ,a_|ende>>
  3. Die Determinante ist abwechselnd: wenn zwei Spalten einer Matrix identisch sind, ist ihre Determinante 0: | a 1 , … , v , … , v , … , a n | = 0. ,dots ,v,dots ,v,dots ,a_|=0.>

Wenn die Determinante wie oben mit der Leibniz-Formel definiert ist, können diese drei Eigenschaften durch direkte Betrachtung dieser Formel nachgewiesen werden. Einige Autoren nähern sich der Determinante auch direkt anhand dieser drei Eigenschaften: Es kann gezeigt werden, dass es genau eine Funktion gibt, die jeder n × n -Matrix . zuordnet EIN eine Zahl, die diese drei Eigenschaften erfüllt. [6] Dies zeigt auch, dass dieser abstraktere Ansatz zur Determinante dieselbe Definition liefert wie der, der die Leibniz-Formel verwendet.

Um dies zu sehen, genügt es, die Determinante durch Multilinearität in den Spalten zu einer (riesigen) Linearkombination von Determinanten von Matrizen zu erweitern, in denen jede Spalte ein Standardbasisvektor ist. Diese Determinanten sind entweder 0 (nach Eigenschaft 9) oder sonst ±1 (nach Eigenschaften 1 und 12 unten), so dass die Linearkombination den obigen Ausdruck in Bezug auf das Levi-Civita-Symbol ergibt. Obwohl sie weniger technisch erscheint, kann diese Charakterisierung die Leibniz-Formel bei der Definition der Determinante nicht vollständig ersetzen, da ohne sie die Existenz einer geeigneten Funktion nicht klar ist. [ Zitat benötigt ]

Sofortige Folgen Bearbeiten

Diese Regeln haben mehrere weitere Konsequenzen:

  • Die Determinante ist eine homogene Funktion, d. h.
  • Das Vertauschen eines beliebigen Spaltenpaars einer Matrix multipliziert ihre Determinante mit −1. Dies folgt daraus, dass die Determinante multilinear und alternierend ist (Eigenschaften 2 und 3 oben):
  • Wenn eine Spalte als Linearkombination der ausgedrückt werden kann andere Spalten (d. h. die Spalten der Matrix bilden eine linear abhängige Menge), ist die Determinante 0. Als Sonderfall beinhaltet dies: Wenn eine Spalte so ist, dass alle ihre Einträge null sind, dann ist die Determinante dieser Matrix 0.
  • Ein skalares Vielfaches einer Spalte zu . hinzufügen Ein weiterer Spalte ändert den Wert der Determinante nicht. Dies ist eine Folge der Multilinearität und der Alternative: Durch die Multilinearität ändert sich die Determinante um ein Vielfaches der Determinante einer Matrix mit zwei gleichen Spalten, die 0 ist, da die Determinante alternierend ist.
  • Wenn A eine Dreiecksmatrix ist, d. h. a i j = 0 =0> , immer wenn i > j oder alternativ immer wenn i < j ist, dann ist seine Determinante gleich dem Produkt der diagonalen Einträge:

Beispiel Bearbeiten

Diese charakterisierenden Eigenschaften und ihre oben aufgeführten Konsequenzen sind beide theoretisch signifikant, können aber auch zur Berechnung von Determinanten für konkrete Matrizen verwendet werden. Tatsächlich kann die Gaußsche Elimination angewendet werden, um jede Matrix in eine obere Dreiecksform zu bringen, und die Schritte in diesem Algorithmus beeinflussen die Determinante auf kontrollierte Weise. Das folgende konkrete Beispiel veranschaulicht die Berechnung der Determinante der Matrix A mit dieser Methode:

füge die zweite Spalte zur ersten hinzu

füge dreimal die dritte Spalte zur zweiten hinzu

vertausche die ersten beiden Spalten

Die Kombination dieser Gleichungen ergibt | A | = − | E | = − 18 ⋅ 3 ⋅ ( − 1 ) = 54.

Transponieren Bearbeiten

Dies kann durch Einsicht in die Leibniz-Formel nachgewiesen werden. [7] Dies impliziert, dass in allen oben genannten Eigenschaften das Wort "Spalte" durchgängig durch "Reihe" ersetzt werden kann. Zum Beispiel das Anzeigen eines nein × nein Matrix als zusammengesetzt aus nein Zeilen ist die Determinante an nein-lineare Funktion.

Multiplikativität und Matrixgruppen Bearbeiten

Somit ist die Determinante a multiplikative Karte, d.h. für quadratische Matrizen A und B gleicher Größe ist die Determinante eines Matrixprodukts gleich dem Produkt ihrer Determinanten:

det ( A B ) = det ( A ) det ( B )

Insbesondere Produkte und Inverse von Matrizen mit einer Determinante ungleich Null (bzw. Determinante Eins) haben diese Eigenschaft noch. Somit bildet die Menge solcher Matrizen (mit fester Größe n ) eine Gruppe, die als allgemeine lineare Gruppe GL n _> (bzw. eine Untergruppe namens spezielle lineare Gruppe SL n ⊂ GL n _subset operatorname _> . Allgemeiner bezeichnet das Wort "speziell" die Untergruppe einer anderen Matrixgruppe von Matrizen der Determinante Eins. Beispiele sind die spezielle orthogonale Gruppe (die, wenn nein 2 oder 3 besteht aus allen Rotationsmatrizen) und der speziellen unitären Gruppe.

The Cauchy–Binet formula is a generalization of that product formula for rectangular matrices. This formula can also be recast as a multiplicative formula for compound matrices whose entries are the determinants of all quadratic submatrices of a given matrix. [9] [10]

Laplace expansion Edit

which is called the Laplace expansion along the i th row. For example, the Laplace expansion along the first row ( i = 1 ) gives the following formula:

Laplace expansion can be used iteratively for computing determinants, but this approach is inefficient for large matrices. However, it is useful for computing the determinants of highly symmetric matrix such as the Vandermonde matrix

This determinant has been applied, for example, in the proof of Baker's theorem in the theory of transcendental numbers.

Adjugate matrix Edit

Thus the adjugate matrix can be used for expressing the inverse of a nonsingular matrix:

Block matrices Edit

If the blocks are square matrices of the gleich size further formulas hold. For example, if C and D commute (i.e., C D = D C ), then there holds [13]

Sylvester's determinant theorem Edit

Sylvester's determinant theorem states that for EIN, an m × nein matrix, and B, an nein × m matrix (so that EIN und B have dimensions allowing them to be multiplied in either order forming a square matrix):

where Im und Inein are the m × m und nein × nein identity matrices, respectively.

From this general result several consequences follow.

  1. For the case of column vector c and row vector r, each with m components, the formula allows quick calculation of the determinant of a matrix that differs from the identity matrix by a matrix of rank 1: det ( I m + c r ) = 1 + r c . >+cr ight)=1+rc.>
  2. More generally, [15] for any invertible m × m matrix X, det ( X + A B ) = det ( X ) det ( I n + B X − 1 A ) , >+BX^<-1>A ight),>
  3. For a column and row vector as above: det ( X + c r ) = det ( X ) det ( 1 + r X − 1 c ) = det ( X ) + r adj ⁡ ( X ) c . c ight)=det(X)+r,operatorname (X),c.>
  4. For square matrices A and B of the same size, the matrices A B and B A have the same characteristic polynomials (hence the same eigenvalues).

Sum Edit

Eigenvalues and characteristic polynomial Edit

The determinant is closely related to two other central concepts in linear algebra, the eigenvalues and the characteristic polynomial of a matrix. Let A be an n × n -matrix with complex entries with eigenvalues λ 1 , λ 2 , … , λ n ,lambda _<2>,ldots ,lambda _> . (Here it is understood that an eigenvalue with algebraic multiplicity μ occurs μ times in this list.) Then the determinant of A is the product of all eigenvalues,

The product of all non-zero eigenvalues is referred to as pseudo-determinant.

The characteristic polynomial is defined as [18]

A Hermitian matrix is positive definite if all its eigenvalues are positive. Sylvester's criterion asserts that this is equivalent to the determinants of the submatrices

Trace Edit

The trace tr(EIN) is by definition the sum of the diagonal entries of A and also equals the sum of the eigenvalues. Thus, for complex matrices A ,

Here exp( A ) denotes the matrix exponential of A , because every eigenvalue λ of A corresponds to the eigenvalue exp( λ ) of exp( A ). In particular, given any logarithm of A , that is, any matrix L satisfying

the determinant of A is given by

For example, for nein = 2 , nein = 3 , and nein = 4 , respectively,

cf. Cayley-Hamilton theorem. Such expressions are deducible from combinatorial arguments, Newton's identities, or the Faddeev–LeVerrier algorithm. That is, for generic n , detEIN = (−1) nein c0 the signed constant term of the characteristic polynomial, determined recursively from

c n = 1 c n − m = − 1 m ∑ k = 1 m c n − m + k tr ⁡ ( A k ) ( 1 ≤ m ≤ n ) . =1

In the general case, this may also be obtained from [20]

where the sum is taken over the set of all integers kl ≥ 0 satisfying the equation

The formula can be expressed in terms of the complete exponential Bell polynomial of nein Argumente sol = −(l – 1)! tr(EIN l ) as

This formula can also be used to find the determinant of a matrix A I J with multidimensional indices I = (i1, i2, . ichr) and J = (j1, j2, . jr) . The product and trace of such matrices are defined in a natural way as

An important arbitrary dimension n identity can be obtained from the Mercator series expansion of the logarithm when the expansion converges. If every eigenvalue of EIN is less than 1 in absolute value,

where I is the identity matrix. More generally, if

is expanded as a formal power series in s then all coefficients of s m for m > nein are zero and the remaining polynomial is det(I + sA) .

Upper and lower bounds Edit

For a positive definite matrix EIN , the trace operator gives the following tight lower and upper bounds on the log determinant

with equality if and only if EIN = I . This relationship can be derived via the formula for the KL-divergence between two multivariate normal distributions.

These inequalities can be proved by bringing the matrix EIN to the diagonal form. As such, they represent the well-known fact that the harmonic mean is less than the geometric mean, which is less than the arithmetic mean, which is, in turn, less than the root mean square.

Derivative Edit

By the Leibniz formula shows that the determinant of real (or analogously for complex) square matrices is a polynomial function from R n × n ^> to R > . In particular, it is everywhere differentiable. Its derivative can be expressed using Jacobi's formula: [21]

Expressed in terms of the entries of A , these are

Yet another equivalent formulation is

Historically, determinants were used long before matrices: A determinant was originally defined as a property of a system of linear equations. The determinant "determines" whether the system has a unique solution (which occurs precisely if the determinant is non-zero). In this sense, determinants were first used in the Chinese mathematics textbook The Nine Chapters on the Mathematical Art (九章算術, Chinese scholars, around the 3rd century BCE). In Europe, solutions of linear systems of two equations were expressed by Cardano in 1545 by a determinant-like entity. [22]

Determinants proper originated from the work of Seki Takakazu in 1683 in Japan and parallely of Leibniz in 1693. [23] [24] [25] [26] Cramer (1750) stated, without proof, Cramer's rule. [27] Both Cramer and also Bezout (1779) were led to determinants by the question of plane curves passing through a given set of points. [28]

Vandermonde (1771) first recognized determinants as independent functions. [24] Laplace (1772) gave the general method of expanding a determinant in terms of its complementary minors: Vandermonde had already given a special case. [29] Immediately following, Lagrange (1773) treated determinants of the second and third order and applied it to questions of elimination theory he proved many special cases of general identities.

Gauss (1801) made the next advance. Like Lagrange, he made much use of determinants in the theory of numbers. He introduced the word "determinant" (Laplace had used "resultant"), though not in the present signification, but rather as applied to the discriminant of a quantic. [30] Gauss also arrived at the notion of reciprocal (inverse) determinants, and came very near the multiplication theorem.

The next contributor of importance is Binet (1811, 1812), who formally stated the theorem relating to the product of two matrices of m columns and nein rows, which for the special case of m = nein reduces to the multiplication theorem. On the same day (November 30, 1812) that Binet presented his paper to the Academy, Cauchy also presented one on the subject. (See Cauchy–Binet formula.) In this he used the word "determinant" in its present sense, [31] [32] summarized and simplified what was then known on the subject, improved the notation, and gave the multiplication theorem with a proof more satisfactory than Binet's. [24] [33] With him begins the theory in its generality.

(Jacobi 1841) used the functional determinant which Sylvester later called the Jacobian. [34] In his memoirs in Crelle's Journal for 1841 he specially treats this subject, as well as the class of alternating functions which Sylvester has called alternants. About the time of Jacobi's last memoirs, Sylvester (1839) and Cayley began their work. Cayley 1841 introduced the modern notation for the determinant using vertical bars. [35] [36]

The study of special forms of determinants has been the natural result of the completion of the general theory. Axisymmetric determinants have been studied by Lebesgue, Hesse, and Sylvester persymmetric determinants by Sylvester and Hankel circulants by Catalan, Spottiswoode, Glaisher, and Scott skew determinants and Pfaffians, in connection with the theory of orthogonal transformation, by Cayley continuants by Sylvester Wronskians (so called by Muir) by Christoffel and Frobenius compound determinants by Sylvester, Reiss, and Picquet Jacobians and Hessians by Sylvester and symmetric gauche determinants by Trudi. Of the textbooks on the subject Spottiswoode's was the first. In America, Hanus (1886), Weld (1893), and Muir/Metzler (1933) published treatises.

Cramer's rule Edit

Linear independence Edit

Orientation of a basis Edit

The determinant can be thought of as assigning a number to every sequence of nein vectors in R nein , by using the square matrix whose columns are the given vectors. For instance, an orthogonal matrix with entries in R nein represents an orthonormal basis in Euclidean space. The determinant of such a matrix determines whether the orientation of the basis is consistent with or opposite to the orientation of the standard basis. If the determinant is +1, the basis has the same orientation. If it is −1, the basis has the opposite orientation.

More generally, if the determinant of EIN is positive, EIN represents an orientation-preserving linear transformation (if EIN is an orthogonal 2 × 2 or 3 × 3 matrix, this is a rotation), while if it is negative, EIN switches the orientation of the basis.

Volume and Jacobian determinant Edit

For a general differentiable function, much of the above carries over by considering the Jacobian matrix of f. For

the Jacobian matrix is the nein × nein matrix whose entries are given by the partial derivatives

Its determinant, the Jacobian determinant, appears in the higher-dimensional version of integration by substitution: for suitable functions f and an open subset U of R nein (the domain of f), the integral over f(U) of some other function φ : R neinR m is given by

The Jacobian also occurs in the inverse function theorem.

Determinant of an endomorphism Edit

The above identities concerning the determinant of products and inverses of matrices imply that similar matrices have the same determinant: two matrices EIN und B are similar, if there exists an invertible matrix X so dass EIN = X −1 BX . Indeed, repeatedly applying the above identities yields

The determinant is therefore also called a similarity invariant. The determinant of a linear transformation

for some finite-dimensional vector space V is defined to be the determinant of the matrix describing it, with respect to an arbitrary choice of basis in V. By the similarity invariance, this determinant is independent of the choice of the basis for V and therefore only depends on the endomorphism T.

Square matrices over commutative rings Edit

The above definition of the determinant using the Leibniz rule holds works more generally when the entries of the matrix are elements of a commutative ring R , such as the integers Z > , as opposed to the field of real or complex numbers. Moreover, the characterization of the determinant as the unique alternating multilinear map that satisfies det ⁡ ( I ) = 1 (I)=1> still holds, as do all the properties that result from that characterization. [41]

The determinant being multiplicative, it defines a group homomorphism

holds. In other words, the displayed commutative diagram commutes.

For example, the determinant of the complex conjugate of a complex matrix (which is also the determinant of its conjugate transpose) is the complex conjugate of its determinant, and for integer matrices: the reduction modulo m of the determinant of such a matrix is equal to the determinant of the matrix reduced modulo m (the latter determinant being computed using modular arithmetic). In the language of category theory, the determinant is a natural transformation between the two functors GL n _> and ( − ) × > . [43] Adding yet another layer of abstraction, this is captured by saying that the determinant is a morphism of algebraic groups, from the general linear group to the multiplicative group,

Exterior algebra Edit

Determinants as treated above admit several variants: the permanent of a matrix is defined as the determinant, except that the factors sgn ⁡ ( σ ) (sigma )> occurring in Leibniz's rule are omitted. The immanant generalizes both by introducing a character of the symmetric group S n > in Leibniz's rule.

Determinants for finite-dimensional algebras Edit

This definition proceeds by establishing the characteristic polynomial independently of the determinant, and defining the determinant as the lowest order term of this polynomial. This general definition recovers the determinant for the matrix algebra A = Mat n × n ⁡ ( F ) _(F)> , but also includes several further cases including the determinant of a quaternion,

the norm [ disambiguation needed ] N L / F : L → F :L o F> of a field extension, as well as the Pfaffian of a skew-symmetric matrix and the reduced norm of a central simple algebra, also arise as special cases of this construction.

Infinite matrices Edit

For matrices with an infinite number of rows and columns, the above definitions of the determinant do not carry over directly. For example, in the Leibniz formula, an infinite sum (all of whose terms are infinite products) would have to be calculated. Functional analysis provides different extensions of the determinant for such infinite-dimensional situations, which however only work for particular kinds of operators.

The Fredholm determinant defines the determinant for operators known as trace class operators by an appropriate generalization of the formula

Another infinite-dimensional notion of determinant is the functional determinant.

Operators in von Neumann algebras Edit

For operators in a finite factor, one may define a positive real-valued determinant called the Fuglede−Kadison determinant using the canonical trace. In fact, corresponding to every tracial state on a von Neumann algebra there is a notion of Fuglede−Kadison determinant.

Related notions for non-commutative rings Edit

For matrices over non-commutative rings, multilinearity and alternating properties are incompatible for nein ≥ 2 , [47] so there is no good definition of the determinant in this setting.

For square matrices with entries in a non-commutative ring, there are various difficulties in defining determinants analogously to that for commutative rings. A meaning can be given to the Leibniz formula provided that the order for the product is specified, and similarly for other definitions of the determinant, but non-commutativity then leads to the loss of many fundamental properties of the determinant, such as the multiplicative property or that the determinant is unchanged under transposition of the matrix. Over non-commutative rings, there is no reasonable notion of a multilinear form (existence of a nonzero bilinear form [ clarify ] with a regular element of R as value on some pair of arguments implies that R is commutative). Nevertheless, various notions of non-commutative determinant have been formulated that preserve some of the properties of determinants, notably quasideterminants and the Dieudonné determinant. For some classes of matrices with non-commutative elements, one can define the determinant and prove linear algebra theorems that are very similar to their commutative analogs. Examples include the q-determinant on quantum groups, the Capelli determinant on Capelli matrices, and the Berezinian on supermatrices (i.e., matrices whose entries are elements of Z 2 _<2>> -graded rings). [48] Manin matrices form the class closest to matrices with commutative elements.

Determinants are mainly used as a theoretical tool. They are rarely calculated explicitly in numerical linear algebra, where for applications like checking invertibility and finding eigenvalues the determinant has largely been supplanted by other techniques. [49] Computational geometry, however, does frequently use calculations related to determinants. [50]

Decomposition methods Edit

For example, LU decomposition expresses A as a product

det ( A ) = ε det ( L ) ⋅ det ( U ) .

Further methods Edit

In addition to the complexity of the algorithm, further criteria can be used to compare algorithms. Especially for applications concerning matrices over rings, algorithms that compute the determinant without any divisions exist. (By contrast, Gauss elimination requires divisions.) One such algorithm, having complexity O ⁡ ( n 4 ) (n^<4>)> is based on the following idea: one replaces permutations (as in the Leibniz rule) by so-called closed ordered walks, in which several items can be repeated. The resulting sum has more terms than in the Leibniz rule, but in the process several of these products can be reused, making it more efficient than naively computing with the Leibniz rule. [53] Algorithms can also be assessed according to their bit complexity, i.e., how many bits of accuracy are needed to store intermediate values occurring in the computation. For example, the Gaussian elimination (or LU decomposition) method is of order O ⁡ ( n 3 ) (n^<3>)> , but the bit length of intermediate values can become exponentially long. [54] By comparison, the Bareiss Algorithm, is an exact-division method (so it does use division, but only in cases where these divisions can be performed without remainder) is of the same order, but the bit complexity is roughly the bit size of the original entries in the matrix times n . [55]

If the determinant of EIN and the inverse of EIN have already been computed, the matrix determinant lemma allows rapid calculation of the determinant of EIN + uv T , where u und v are column vectors.


There Is No Such Thing as ‘White’ Math

JackGarner March 5, 2021 at 8:05 pm

Thank you all at Winter Watch for allowing me to Vent, for understanding my Passion for US. Please bear with me, as I have much to say.

Wow, it now appears that anything difficult to learn and/or has any normal challenge to at all, it is deemed systematic white racism by “The Great Awokening”. Supposing waking up for the Awoke every morning is sometimes hard, too so maybe the Awoke should just permanently sleep-in, and we Patriotic Americans will take care of the rest of US.

Complaining, Executive-level Public Corruption, and it’s easy way out (Crime) have now Cocktailed unclean hands on a large enough scale to have created its own Economy, separate from US/Ours. It was all clearly staged and put into play by the Democrat Party Leadership’s Clandestine Political Arena – Their Deep State. Though, none of US wanted or want to see any violence, “The Great Awokening and Democrat Party Leadership” are, without question, intentionally inciting violence, trying desperately to make it happen, just like a False-Flag Op to gain the necessary public support to maintain Absolute Power for Communist-China’s next move, via JOETUS.

Never mind US, Right! It’s just Common Sense 101 (God’s Gravity), and the S is about to HTF. Sad, but true. Never thought I’d see these days, but they are clearly upon US All.

My 31-year career as a private contractor was filled with Great Respect for FBI and our US Intelligence Community, and there is absolutely no shortage of evidence to prove it. As for now, our Country needs the FBI and our Intelligence Community more than ever before. So they had better Cocktail-Up for US American Citizens, and once and for All, stop this living-breathing-metastasizing Democrat Party Leadership Deep-State Coup deTat’ of our US Government, of our Country, of US All. Our FBI and Intelligence Community swore to defend our Constitutional Rights against Enemies, Both Foreign and Domestic. And so far, None of US are giving up our Constitutional Rights as US Citizens to JOETUS, the Democrat Party Leadership, or to their Deep-State.

I have seen and survived much in my over 60 years of life, and have always worked the right side of the fence, never the Dark-Side I will go to my grave in knowing so. And, FBI and some in the Intelligence Community know it. I started losing trust in FBI when in 2009, they admonished me, and now I know why (for getting far too close to exposing the Clintons-Obama-Joe Biden). None of US Patriotic Americans want any violence at all, as we entrusted in our FBI and Intelligence Community to protect US from it. Nor did any of US True Trump Supporters, paying close attention to his end message of Transparency, Truth and Justice, want any violence. Nor do I – in any way – have any intent to incite any violence, never have, and never will.

On another note, with the exception of a few Heroic FBI Agents still on the job, most of the FBI I knew of years ago have retired, many because they served their time well and saw what was coming in 2008 – those Agents were and still are Good Men and Women. They honored their Service Commitments and Protected US Well. As for the rest of you newer Agents, please remember what you stand for. This should make some sense to you As my Father, the Colonel once told me at the young age of 10 (just after a 4-year old Muslim boy was sacrificed and another Good, Decent Moderate-Muslim Friend was Murdered in front of US 12 Americans being held hostage in the Middle-East for 4 hours that day), “Son, pull yourself up by your bootstraps, know we love you, and you’re going to be alright, as long as you get up and move forward with me again. Walk with me, Son. We’re here for a reason – these people need our help.” We 12 Americans physically fought off terrorists that day and the US Navy Sixth Fleet and US Marines aboard that 1969 Med-Flotilla backed up the 4 Israeli-Trained Commandos who saved US.

What say you FBI, our Intelligence Community? Who do you Serve & Protect? As long as you do what it Right and Just, we will always support you. Keeping you All in Prayer, as well, and let God’s Gravity handle the rest.

The Evergreen State College -BLM problem like.( BLM members were pissed off when Soros didn’t pay them as he said he would , for them to make a huge mess…)
Here the aim is to make stupid average people easy to tell what to do and what to think, plus making people watch this while they buy guillotines or do anything else that they do not want us to notice.


Physics Buzz

An interwebs firestorm has been raging recently about a Numberphile video that makes the astounding claim that if you add up all the positive whole numbers from one to infinity, the result will be -1/12. To write it out more concisely

1+2+3+4+ . . . = -1/12 , (where the three dots indicate all the rest of the positive numbers up to infinity)

If you haven't seen the video, take a look - it's short.


Renowned science writer and astronomer Phil Plait (Bad Astronomy) blogged about the video recently, calling it "simply the most astonishing math you'll ever see." The post led to a Twitter and comment storm, fueled both by people bowled over by the calculation and a much larger number of people convinced it was nothing short of mathematical fraud.The passionate response he got to his post led Plait to write a follow up piece, partly in self defense, and partly as penance for his various mathematical sins as pointed out by his readers.

Clearly, only a fool would consider defending this absurd calculation after the reception Plait got.

I'm not going to follow Plait's example of trying to explain the math that goes into the calculation. But I will point out that many of the problems that commenters and Twitterers latched onto are irrelevant if you look at the more elaborate discussion in the Numberphile's extra footage. In the much longer second video, they come to the same reviled result as in the first video, except that they use an approach first written down by Leonhard Euler.

If you dislike the initial video, you really should watch this one to see if it sways you at all.

That's much better, isn't it? I'm sure it's not perfect, but the flaws are beyond my mathematical abilities to recognize.

In any case I'm willing to believe 1+2+3+4+ . . . = -1/12 is a mathematically legitimate thing to write down for the following three reasons.

1. Euler, who was one of the greatest mathematicians of all time, proved the equation for real numbers.

2. Another great mathematician, Bernhard Riemann, generalized Euler's approach to include complex numbers, and came up with the same equation.

3. My favorite mathematician, the self-taught genius Srinivasa Ramanujan, rediscovered the equation and stood by it, even though he realized that he might be thought be mad for making the claim, writing in a letter to mathematician G.H. Hardy, "I told him that the sum of an infinite number of terms of the series: 1 + 2 + 3 + 4 + · · · = 𕒵/12 under my theory. If I tell you this you will at once point out to me the lunatic asylum as my goal."

So, counting the Numberphiles' somewhat dubious derivation, there are at least four ways to prove that the sum of all the positive integers equals -1/12. And as far as I know, there's no way to prove that it doesn't equal -1/12.*

If you don't believe any of these people, then there's nothing I can do, mathematically speaking, to change your mind. I mean these guys are among the greatest. What could I add that would improve on their proofs?

But, Obviously 1+2+3+4+ . . . = -1/12 Doesn't Really Mean Anything - Right?

Of the mathematicians and physicists I've talked to about it, several of them are willing to accept that it's possible to derive the equation, but insist that it's meaningless. They tell me, if I understand them correctly, that it's some sort of numeric fluke that can't possibly have any consequences in the real world. There's just no way to add positive numbers together get a negative result in reality, especially when the numbers you're adding are getting larger and larger. In effect, it's nothing more than an artifact that results from a method that makes sense when applied to complex variables or other series, but not for the sum of positive integers. To think otherwise would be nuts, right?

The problem is, they're wrong (or so a number of physicists have told me). The equation 1+2+3+4+ . . . = -1/12 is vital for describing the real world.

As the Numberphile people point out, the dreaded equation pops up in many places in physics. They specifically note it's appearance in a string theory textbook (see page 22 in this Google book). But that's only one example and, depending on how you feel about string theory, among the least convincing ones. What's much more compelling is the fact that this sort of equation is integral to Quantum Electrodynamics (QED).

QED is the theory that explains the interaction between charged particles like electrons and protons. Along with neutrons, electrons and protons make up atoms, which in turn make up molecules and everything built of them. In other words, QED essentially describes much of the physical world we live in. And it does it extremely well. QED calculations for the spin of the electron have been confirmed to better than one part in ten trillion - making QED just about the most precise and successful theory of all time.

If QED is correct (and it appears to be the most correct theory yet developed, if experimental confirmation is a reasonable way to judge correctness), then I would argue that the things that go into QED calculations must be just as correct. Doing QED calculations requires using 1+2+3+4+ . . . = -1/12, so the equation is at least as correct as QED theory itself.

In fact, the Wikipedia page on a QED phenomenon known as the Casimir Effect shows a derivation of the effect that includes an even more audacious equation involving the sum of the cubes of the natural numbers up to infinity. Specifically, calculating the effect involves using the equation


1^3+2^3+3^3 +4^3+ . . . = 1/120, (where the notation 2^3 means 2x2x2)

(In the Wikipedia article, they have an equation that looks like this , but the stuff on the left hand side is just another way of writing 1^3+2^3+3^3 +4^3+ . . .)

The number on the right is positive this time, but it's ten times smaller than 1/12, even though each of the terms in the sum is much bigger than the corresponding terms in the equation 1 + 2 + 3 + 4 + . . . = 𕒵/12 (except for the first term, of course, since 1^3 = 1). Both equations come from the same sort of derivation, so it's not surprising that they are both seemingly incredible and ridiculous. But if you believe in QED and the Casimir Effect, how can you not believe the pieces that go into them?

Maybe It's Just a Trick

One response I've gotten after querying my more mathematically savvy friends is that the equations are nifty tricks, and nothing more, to get rid of infinities in QED and produce the correct finite answers. I guess that's possible, but you would have to be one heck of a mathamagician to come up with a trick resulting in accuracy of a part in ten trillion.

It's even more impressive when you consider that the QED predictions came before the experiments that measured things like the electron spin to fourteen decimal places. It's one thing to design a trick to rationalize a number you already know. It's a whole other matter to come up with a trick that gives you the answers in advance of the experiment. In that case, it's not a trick, it's simply a very good theory.

Maybe It's Not Necessary, Just Handy

One final possibility that I can think of is that the equations are not really necessary for doing QED calculations, and that instead there is a correct and intelligible approach that gives answers without using nonsense like 1 + 2 + 3 + 4 + . . . = 𕒵/12 or 1^3+2^3+3^3 +4^3+ . . . = 1/120.

I can't imagine why physicists would rather rely on trickery than doing things correctly, so I tend to dismiss the idea that some sort of mathematical conspiracy is behind it all. If it turns out that it's possible to have physical theories that describe the real world as well as QED does without relying these equations, then we might as well use those theories and forget the whole controversy.

So What's Really Wrong?

If you accept that Euler, Riemann, and Ramanujan did things properly when they found 1 + 2 + 3 + 4 + . . . = 𕒵/12, and if you accept that it and related equations are necessary to describe the real world, then how can you not accept that the equation is true? And yet, many people still claim that there's something wrong. It doesn't make sense. It's so counter intuitive that the phrase "counter intuitive" seems far too weak a description. It's an alien, freakish, mind f----.

But that's OK. Some things are true without being conceivable. This is just the most recent example I can think of. Pythagoras and and his followers apparently committed human sacrifice because they couldn't handle the idea of irrational numbers. For centuries, ancient mathematicians struggled with unsolvable problems because they didn't know that pi is a transcendental number. And today, there are still things about quantum mechanics that defy intuitive understanding - the whole point of Schrodinger's Cat is to illustrate the absurdity of quantum superposition. But just because people didn't intuitively grasp those things, it didn't change the fact the the square root of 2 is irrational, that pi's transcendental nature means it's impossible to square the circle, and that particles can become quantum mechanically entangled just like Schrodinger's Cat.

Yes, there's a problem with 1 + 2 + 3 + 4 + . . . = 𕒵/12. But I suspect the problem is with us and our failure to understand infinity. Why shouldn't an infinite sum of numbers going to infinity add up to a finite (and negative!) number? I don't really know what infinity means anyway, so I can't think of any way to object to a statement that includes not one but TWO infinities in it.

You might as well ask me why a bandersnatch of numbers going to bandersnatch add up to -1/12. But if you're able to mathematically sum a bandersnatch of bandersnatches, and then use that sum to describe the real world and predict the outcomes of real world experiments I have no choice but it seems unreasonable not to believe your bandersnatch math.


1.2: Naïvely - Mathematics

1.2.7 Non - commutativity of rules substitution

Let us look at the last of the 3 definitions of < f > in the above example. It implies that any input object has to be replaced by its Sine. Naively, this would mean that we should have obtained Sine-s of all our expressions, but this did not happen. The point is that the sequential rule application is non-commutative: first of all, the way rules are applied is such that once the first rule that applies is found, only this rule is applied, and other possibly matching rules are not tried on a given (sub)expression, in a single "run" of the rule application. Second, if several rules match an expression, the first applied rule rewrites it so that (some) of other rules don't match it any more. Therefore, the result depends on the order in which the rules are applied. Mathematica applies rules to expressions sequentially. Since the rule with the Sine function was defined last, it should mean that it has a chance to apply only to inputs whose form did not match patterns in the first two rules.


We must evaluate any exponents before we add, subtract, multiply or divide. For example, in the expression 2 3 + 3 × 2 2 2^3 + 3 imes 2^2 2 3 + 3 × 2 2 , we could obtain a variety of different answers if we changed the order of operations.

The correct ordering requires the evaluation of exponents first, which gives the following: 2 3 + 3 × 2 2 = 8 + 3 × 4 = 8 + 12 = 20 2^3 + 3 imes 2^2 = 8 + 3 imes 4 = 8 + 12 = 20 2 3 + 3 × 2 2 = 8 + 3 × 4 = 8 + 1 2 = 2 0 , which is now correct.

What is 3 2 × 2 + 4 3 3^2 imes 2 + 4^3 3 2 × 2 + 4 3 ?

Following the correct order of operations, we see that we must evaluate the exponents first. This gives 3 2 × 2 + 4 3 = 9 × 2 + 64 = 18 + 64 = 82. □ 3^2 imes 2 + 4^3 = 9 imes 2 + 64 = 18+64 = 82. _square 3 2 × 2 + 4 3 = 9 × 2 + 6 4 = 1 8 + 6 4 = 8 2 . □ ​


Schreier-Sims Algorithm

To describe the Schreier-Sims algorithm, we use the following notations:

  • is some subset represented in the computer’s memory
  • is a subgroup of
  • G acts on the set

Let us pick some random element and consider its orbit under G. From the theory of group actions, we have

where is the isotropy group of k. Now it is easy to compute the orbit of k: we start by setting the orbit to be the singleton <k>, then expand it by letting elements of EIN act on elements of this set. The process stops if we can’t add any more elements via this iteration. A more detailed algorithm will be provided later.

Thus, if we could effectively obtain a set of generators for , our task would be complete since we could recursively apply the process to . [Or so it seems: there’ll be a slight complication.]

For that, we pick a set U of representatives for the left cosets as follows. For each , we pick some element which maps , and for j = k we pick the identity. To facilitate this process, we use a data structure called a Schreier vector.


2 Antworten 2

I'm not sure about the bonus but here's the best you can do for the main part

Proof that this is the best

Ignore the first equation and consider the sum of both sides of the other four equations. This gives us that the sum of fourteen distinct positive integers is equal to $4N$ . The sum of fourteen distinct positive integers is at least $105$ so we have $4N geq 105$ or $N geq 26.25$ . Hence $N geq 27$

Lower bound for the bonus

Let's say we use the same reasoning to try to obtain a lower bound and there are $n$ equations. Then ignoring the first equation we will have $frac<2>$ distinct positive integers on the left hand side which sum to $(n-1)N$ . The smallest possible value of the sum of $frac<2>$ distinct positive integers is $frac<(n^2+n-2)(n^2+n)><8>$ so we have that $ N geq frac<(n^2+n-2)(n^2+n)> <8(n-1)>= frac<8>$ or, since we know it is an integer $N geq leftlceil frac <8> ight ceil$

Improving this bound for larger $n$ (credit to Greg Martin in the comments for this idea)

If we ignore roughly the first $frac<3>$ equations and just consider the rest then we'll have roughly $frac<4n^2 + 3n><9>$ positive integers on the left hand side which sum to $frac<2nN><3>$ and since the sum of the first $frac<4n^2 + 3n><9>$ positive integers is $frac<(4n^2 + 3n)(4n^2+3n+9)><162>$ we obtain $ frac<2nN> <3>geq frac<(4n^2 + 3n)(4n^2+3n+9)><162>$ or $ N geq frac<16n^3+24n^2+45n+27> <108>> frac<4n^3><27>$ Greg Martin found the cutoff point $frac<2n><3>$ by optimization.
Already at $n=6$ we see this bound take over where the value of $frac<16n^3+24n^2+45n+27><108>$ is $42.75$ but for my original bound it's $42$ .

The OIES entry for the sequence A047837 calls this "Honaker's triangle problem" and says that the optimal $N$ is conjectured to equal:

(sequence A047873), where $T(n)=n(n+1)/2$ , the $n$ -th triangular number. The OIES entry refers to the book The Zen of Magic Squares, Circles and Stars by Clifford A. Pickover, who attributes the problem to math teacher and author G.L. Honaker, Jr. Pickover gives the same expression (in simplified form) as a lower bound on the sum $M$ :

(This is equal to the above expression at the maximal value of $r=lfloor n/3 floor+1$ .) This bound is credited to Mike Keith and Judson McCraine, who conjecture this bound is exact and have verified it "for all $n$ up to several hundred" (the OEIS says $n<365$ ). Unfortuately the trail of references ends here, as Pickover cites personal communication with Keith.

Note that the bound can be derived using the method described by hexomino, as shown below.

The triangle with $n$ rows has $T(n)$ entries, and similarly the portion of the triangle above row $r$ (i.e. up to row $r-1$ ) has $T(r-1)$ entries. Therefore the trapezoid from rows $r$ to $n$ has $k=T(n)-T(r-1)$ entries. Die Summe der Einträge ist gleich der Zeilensumme $N$ mal der Anzahl der Zeilen, $n-(r-1)=n-r+1$ . Da diese Einträge verschieden sein müssen, darf ihre Summe nicht kleiner sein als die Summe der ersten $k$ ganzen Zahlen, also $T(k)=T(T(n)-T(r-1))$ . Diese zusammensetzen ergibt:

Da dies für alle $rin[1,n]$ gilt, können wir das Maximum über alle $r$ als untere Grenze für $n$ nehmen (und da $N$ eine ganze Zahl ist, können wir die Obergrenze als Gut). Der Ausdruck ist kubisch in $r$ , mit einer Ableitung von:

Die Ableitung hat Wurzeln bei:

Die Ableitung ist eine nach unten gerichtete Parabel, so dass der Ausdruck vor der ersten Wurzel abnimmt, zwischen den beiden Wurzeln steigt und nach der zweiten Wurzel abnimmt. Die erste Wurzel tritt jedoch auf, wenn $r<0$ so ist, dass für den Bereich, an dem wir interessiert sind, der Ausdruck vor der positiven Wurzel ansteigt und danach abnimmt. Dies bedeutet, dass das Maximum für $rinmathbb$ tritt beim positiven Wert von $r^*$ auf, und das Maximum für $rinmathbb$ wird auf dem Boden oder der Obergrenze von $r^*$ auftreten.

Wir können dies sowie $a<sqrt . verwenden$ , um den Quadratwurzelterm im Ausdruck für das Optimum $r$ zu begrenzen:

Wenn wir schließlich $nge 1$ nehmen, dann ist $frac<1><2n+1>le frac<1><3>$ , also können wir binden:

Daraus können wir bestimmen, dass der optimale Wert für $rinmathbb$ ist einer von $lfloor (n+2)/3 floor=lceil n/3 ceil$ oder $lceil n/3 ceil+1$ . Um zu bestimmen, welche, müssen wir drei Fälle betrachten:

$ egin n&=3k & lceil n/3 ceil &= k n&=3k+1 & lceil n/3 ceil &= k + 1 n&=3k+2 & lceil n/3 ceil & = k + 1 end $

Für jeden dieser Fälle sind die beiden Grenzen für $n$:

$ egin <|c|c|c|>hline n & N(r=lceil n/3 ceil) & N(r=lceil n/3 ceil+1) hline 3k & 4k^3+ 2k^2+k & 4k^3+2k^2+frac<5><4>k+frac<1> <4> hline 3k+1 & 4k^3+6k^2+4k+1 & 4k^3+6k^2+frac<13><4>k+frac<3> <4> hline 3k+2 & 4k^3+10k^2+frac<37><4> k+3 & 4k^3+10k^2+9k+3 hline end $

Für den Fall $n=3k$ ist die rechte Spalte ( $r=lceil n/3 ceil+1$ ) größer, während für die anderen beiden die linke Spalte größer ist ( $r=lceil n/3 ceil$ ). Beachten Sie jedoch, dass $lceil n/3 ceil=lfloor n/3 floor$ ist, wenn $n$ durch 3 teilbar ist und $lceil n/3 ceil=lfloor n/3 floor+1$ wenn $n$ nicht durch 3 teilbar ist, also können beide Fälle vereinfacht werden auf:


Schau das Video: KSSM Matematik Tingkatan 3 Bab 1 indeks permudahkan setiap yang berikut uji minda no1 buku teks (Oktober 2021).